@TOC
这里介绍双指针在数组中的第一类题型：一个数组当两个用。
第一题
88. 合并两个有序数组
题目描述：
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例1：
1
2
3
4
| 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
|
思路
一个简单的想法，借助新建数组nums3来完成nums1和nums2的合并。如果nums1[0]小于nums2[0]，则将nums1[0]放入nums3[0]，继续比较nums1[1]和nums2[0]。同样的，如果nums2[0]小于nums1[0]，则将nums2[0]放入nums3[0]，继续比较nums2[1]和nums1[0]。直到将nums1或nums2遍历完，剩下未遍历的部分可以直接放入nums3。
但是，题目要返回的是nums1而不是nums3。那么我们有两个办法来对上述的方法进行优化。第一个办法，最后遍历nums3，用nums3的元素替换nums1的元素。第二个办法，直接在nums1上进行上述的操作。如果要在nums1上进行上述的操作，那么就需要从大到小比较，先把最大的元素放到nums1最右侧，以免覆盖了未参与比较的nums1元素。
直接把nums1数组当nums3数组来用，就是双指针的精髓所在。
代码
java版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int idx1 = m-1, idx2 = n - 1, idx = m + n - 1;
while(idx1>=0 || idx2 >=0){
if(idx1 < 0){
nums1[idx--] = nums2[idx2--];
}
else if(idx2 < 0){
nums1[idx--] = nums1[idx1--];
}
else if(nums1[idx1] > nums2[idx2]){
nums1[idx--] = nums1[idx1--];
}
else{
nums1[idx--] = nums2[idx2--];
}
}
}
}
|
python版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
idx1, idx2, idx3 = m - 1, n - 1, m + n - 1
while idx1 >= 0 and idx2 >= 0:
if nums1[idx1] > nums2[idx2]:
nums1[idx3] = nums1[idx1]
idx3 -= 1
idx1 -= 1
else:
nums1[idx3] = nums2[idx2]
idx3 -= 1
idx2 -= 1
while idx3 >= 0 and idx2 >= 0:
nums1[idx3] = nums2[idx2]
idx3 -= 1
idx2 -= 1
|
第二题
27. 移除元素
题目描述：
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例1：
1
2
3
| 输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
|
思路
如果不要求原地修改，那很简单。只需要新建数组nums1，从左到右扫描nums的元素，如果nums的元素不等于val，则将其放入nums1；如果等于val，则跳过。
但是，现在要求原地修改，也就是要一个数组当作两个用。和上一题一样，有两种办法。第一种办法，可以先把元素放在数组nums1，然后再用nums1的元素去覆盖nums的元素。第二种办法，可以直接把nums数组当nums1数组。但是，这样会不会导致nums原有的元素被覆盖呢？实际上是不会的，我们思考一下，如果用idx1扫描nums，非val元素通过idx2存放到nums1，那么idx1总是大于等于idx2的。也就是说，idx2使用的区域，idx1早就扫描过了。
代码
java版本
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int removeElement(int[] nums, int val) {
int slow = 0;
int fast = 0;
for(; fast < nums.length; fast++){
if(nums[fast] != val){
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
}
|
python版本
1
2
3
4
5
6
7
8
9
10
| class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
n = len(nums)
slow, fast = 0, 0
while fast < n:
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow
|
第三题
283. 移动零
题目描述：
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例1：
1
2
| 输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
|
思路
这题和上一题很相似，都是遇到val（0）就跳过。但是不同的是，这道题不仅要跳过val，还要把val放到后面去。有两种办法，第一种是和第二题一样，遇到val的时候就跳过val，然后再把后面都填充为val；第二种是让val和非val进行交换。
代码
java版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public void moveZeroes(int[] nums) {
int slow = 0;
int fast = 0;
final int val = 0;
for(; fast < nums.length; fast++){
if(nums[fast] != val){
int temp = nums[slow];
nums[slow] = nums[fast];
nums[fast] = temp;
slow++;
}
}
}
}
|
python版本
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
slow, fast = 0, 0
while fast < n:
if nums[fast] != 0:
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1
fast += 1
|
第四题
26. 删除有序数组中的重复项
题目描述：
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例1：
1
2
3
| 输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
|
思路
如果不是原地修改，那我们还是考虑新建数组nums1。nums[0]肯定是不重复的，可以放到nums1[0]。因为nums是有序的，从nums[1]开始，如果和前面的元素相同，那么说明是重复的，可以跳过；如果和前面的元素不同，那么说明不重复，放入nums1数组。
如果要原地修改，还是同样的情况，有两种办法。第一种办法就是用nums1去覆盖nums。第二种办法，要一个数组当作两个用。我们总是要思考，会不会覆盖未扫描的元素？看得出，fast总是比slow跑得快，所以不会覆盖。
代码
java版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int removeDuplicates(int[] nums) {
int slow = 0;
int fast = 0;
for(; fast < nums.length; fast++){
if(nums[fast] != nums[slow]){
slow += 1;
nums[slow] = nums[fast];
}
}
return slow + 1;
}
}
|
python版本
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
n = len(nums)
slow, fast = 0, 0
while fast < n:
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
fast += 1
return slow + 1
|
下一篇博客LeetCode算法题解——双指针2中，我将分享LeetCode中另一种类型的双指针问题。
参考：
Leetcode 题解 - 双指针