Leetcode 刷题笔记(二) —— 数组类型解题方法二：双指针法
刷题路线来自 ：代码随想录
快慢双指针法
因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就要移动其他元素的地址。所以数组中元素的删除实则是后边元素对前边元素的覆盖，这时就要用到双指针法。
27. 移除元素
Leetcode 链接
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
方法一：暴力解法
- 一层循环寻找要删除的数的下标
- 二层循环，在找到要删除的数时，从该位置开始后边的数向前覆盖
class Solution {
public int removeElement(int[] nums, int val) {;
int len = nums.length;
for (int i = 0; i < len; i ++) {
if (nums[i] == val) { // 找到要移除的元素，后边所有元素向前移动
for (int j = i + 1; j < len; j ++) {
nums[j - 1] = nums[j];
}
len --; // 长度减1
i --; // 因为原地移除了该元素，所以下一轮循环还是从该下标开始
}
}
return len;
}
}
方法二：快慢指针（双指针法）
- 快指针找到要删除的数时，慢指针不动，快指针加一；
- 快指针没有找到要删除的值时，慢指针位置拷贝快指针位置的值，快慢指针各加一
class Solution {
public int removeElement(int[] nums, int val) {
int slow = 0;
for (int fast = 0; fast < nums.length; fast ++) {
if (nums[fast] != val) {
nums[slow++] = nums[fast];
}
}
return slow;
}
}
26. 删除有序数组中的重复项
Leetcode 链接
26. 删除有序数组中的重复项
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2]
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
题解：
- fast 与 fast-1 相同时，fast++,慢指针 slow 不动
- 慢指针在fast 找到第一次出现的数后， fast 与 fast-1 不同时，
class Solution {
public int removeDuplicates(int[] nums) {
int slow = 1;
for (int fast = 1; fast < nums.length; fast++) {
if (nums[fast] != nums[fast - 1]) {
nums[slow++] = nums[fast];
}
}
return slow;
}
}
283. 移动零
Leetcode 链接
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。必须在原数组上操作，不能拷贝额外的数组。尽量减少操作次数。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
题解：
方法一：移除 0 后，从慢指针开始后边全部赋 0 即可
class Solution {
public void moveZeroes(int[] nums) {
int slow = 0;
for (int fast = 0; fast < nums.length; fast ++) {
if (nums[fast] != 0) {
nums[slow++] = nums[fast];
}
}
for (int i = slow; i < nums.length; i ++) {
nums[i] = 0;
}
}
}
方法二：直接互换快慢指针位置的数，可减少一次遍历。
动图
class Solution {
public void moveZeroes(int[] nums) {
int slow = 0;
for (int fast = 0; fast < nums.length; fast ++) {
if (nums[fast] != 0) {
// 放在fast 和 slow 位置相同时的多余操作
if (fast > slow) {
int temp = nums[slow];
nums[slow] = nums[fast];
nums[fast] = temp;
}
slow ++;
}
}
}
}
844. 比较含退格的字符串
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。如果相等，返回 true ；否则，返回 false 。如果对空文本输入退格字符，文本继续为空。
示例 1：
输入：s = “ab#c”, t = “ad#c”
输出：true
解释：S 和 T 都会变成 “ac”。
示例 2：
输入：s = “ab##”, t = “c#d#”
输出：true
解释：s 和 t 都会变成 “”。
示例 3：
输入：s = “a##c”, t = “#a#c”
输出：true
解释：s 和 t 都会变成 “c”。
示例 4：
输入：s = “a#c”, t = “b”
输出：false
解释：s 会变成 “c”，但 t 仍然是 “b”。
题解： 快指针找 ’#‘，慢指针为被覆盖位置。
- 在快指针位置不为 ’#‘ 时，慢指针位置覆盖快指针位置的值
- 在快指针找到 ’#‘ 时，只需将慢指针回退一个位置
class Solution {
public boolean backspaceCompare(String s, String t) {
return convert(s).equals(convert(t));
}
public String convert(String s) {
char[] ch = s.toCharArray();
int slow = 0;
for (int fast = 0; fast < s.length(); fast++) {
if (ch[fast] != '#') {
ch[slow++] = ch[fast];
} else {
if (slow > 0) {
slow --;
}
}
}
return String.valueOf(ch).substring(0, slow);
}
}
总结
数组中移除元素类型的题，使用双指针的快慢指针法可以方便的解题：快指针遍历数组，去找符合题目条件的元素，慢指针位置始终为指向要被覆盖的位置，在没有找时，慢指针位置正常被覆盖。
首尾双指针法
977. 有序数组的平方
Leetcode 链接
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
题解： 因为原本是有序排列，所以平方后是两头大中间小，从中间往两边是有序的，那么我们可以使用双指针从两边向中间遍历
class Solution {
public int[] sortedSquares(int[] nums) {
int len = nums.length;
int left = 0;
int right = len - 1;
// 返回数组
int[] res = new int[len];
int i = len - 1;
while (left <= right) {
if (nums[left] * nums[left] >= nums[right] * nums[right]) {
// 左边大，左指针向右移动
res[i] = nums[left] * nums[left];
left++;
} else {
// 右边大，右指针向左移动
res[i] = nums[right] * nums[right];
right--;
}
// 返回数组最大值下标向左移动
i--;
}
return res;
}
}