算法中双指针的技巧应用

1. 技巧

1.1 情景一

通常情况下,我们都是只使用从第一个元素到最后一个数结束的一个指针来进行迭代。但是,我们可能需要同时使用两个指针进行迭代。

例如反转数组中的元素,其解决算法的思想是:将第一个元素和末尾进行交换,再向前移动到下一个元素,并不断地交换,直到它到达中间位置。我们可以应用双指针来完成迭代:一个从第一个元素开始,另一个从最后一个元素开始。持续交换它们所指向的元素,知道这两个指针相遇,伪代码如下:

1
2
3
4
5
6
7
8
9
public static void reverse(int[] v, int N) {
int i = 0;
int j = N - 1;
while (i < j) {
swap(v, i, j); // 自定义的交换元素的方法
i++;
j--;
}
}

总之,双指针的应用场景一是用在:需要从两端向中间迭代数组的情况。具体的操作为:一个指针从始端开始,而另一个指针从末端开始。

1.2 情景二

双指针的应用场景二是使用两个不同步的指针来解决问题。例如一道使用原地算法移动元素的题如下:

1
给定一个数组和一个值,原地删除该值的所有实例并返回新的长度。

如果我们没有空间复杂度上的限制,那就更容易了。我们可以初始化一个新的数组来存储答案。如果元素不等于给定的目标值,则迭代原始数组并将元素添加到新的数组中。

实际上,它相当于使用了两个指针,一个用于原始数组的迭代,另一个总是指向新数组的最后一个位置。

但是,如果我们考虑空间的限制,则可以使用双指针的策略:一个仍然用于迭代,而第二个指针总是指向下一次添加的位置

1
2
3
4
5
6
7
8
9
10
public int removeElement(int[] nums, int val) {
int j = 0; // 慢指针,指向下一次元素添加的位置
for (int i = 0; i < nums.length; i++) {
if (nums[i] != val) {
nums[j] = nums[i];
j++;
}
}
return j;
}

可以看到,在上面的Solution中,使用了一个快指针i和慢指针ki每次都移动一步,而k只在添加新的被需要的值时才移动一步。

2. 应用

2.1 两数之和

题目(原题见Leetcode)

1
2
3
4
5
6
7
8
9
10
11
12
给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。
说明:

1. 返回的下标值(index1 和 index2)不是从零开始的。
2. 你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。

示例:

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

该题如果使用的是单指针双循环来实现,虽然容易实现,但是算法执行的效率非常的低,高达160ms+

1
2
3
4
5
6
7
8
9
10
public int[] twoSum(int[] numbers, int target) {
for (int i = 0; i < numbers.length; i++) {
for (int j = i + 1; j < numbers.length; j++) {
if (numbers[i] + numbers[j] == target) {
retrun new int[]{i + 1, j + 1}
}
}
}
return null;
}

但是如果使用双指针技巧,根据和与目标数的大小来选择是左指针向后移动(总数将变大)还是右指针向前移动(总数将变小):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] twoSum(int[] numbers, int target) {
int l = 0; // 左指针
int r = numbers.length - 1; // 右指针

while (l < r) {
if (numbers[l] + numbers[r] == target) { // 符合题意
return new int[]{l + 1, r + 1};
} else if (numbers[l] + numbers[r] > target) {
/* 如果和大于目标数,则将右指针往前移动,将右指针指向的数减小 */
r--;
} else {
/* 如果和小于目标数,则将左指针往后移动,将左指针指向的数增大 */
l++;
}
}
return null;
}

执行的时间是1ms,可以看到差距非常的大。

2.2 长度最小的子数组

题目(原题见Leetcode)

1
2
3
4
5
6
7
给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。

示例:

输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

该题的解决的核心思想就是维护双指针,即一个快指针和一个慢指针,并确定两个指针的移动策略

主要的处理逻辑是:首先将元素尽量多的累计起来,让它们的和超过s,再按数组的索引和慢指针的递增,从小到大去掉一些元素,使元素的和逼近s, 并保持元素的和大于等于s。这样可以找出所有的情况:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int minSubArrayLen(int s, int[] nums) {
if (nums == null || nums.length == 0) return 0;

int len = nums.length;
int res = Integer.MAX_VALUE;
int left = 0; // 慢指针
int sum = 0;

for (int i = 0; i < len; i++) {
sum += nums[i]; // 把前i个元素累加起来,让它们的和超过s
while (sum >= s) {
res = Math.min(res, i - left + 1); // 记录i-left+1,即相加的元素个数
sum -= nums[left]; // 依次剔除元素,使sum尽量接近s
left++;
}
}
return (res != Integer.MAX_VALUE) ? res : 0;
}

测试用例:

1
2
3
4
5
6
7
8
int s = 7;
int[] nums = {2, 3, 1, 2, 4, 3};

Solution solution = new Solution();
int res = solution.minSubArrayLen(s, nums);
System.out.println("res:" + res);

// 打印结果为:res:2

2.3 删除排序数组中的重复项

题目(原题见Leetcode)

1
2
3
4
5
6
7
8
9
10
11
12
给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。
不要使用额外的数组空间,你必须在原地修改输入数组并在使用 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

你不需要考虑数组中超出新长度后面的元素。

对于这种原地算法解决问题,也可以尝试使用双指针来实现。同样,一个是快指针i,用于迭代;一个是慢指针j,只有当元素不相等时才递增:

1
2
3
4
5
6
7
8
9
10
11
12
public int removeDuplicates(int[] nums) {
if (nums == null || nums.length == 0) return 0;

int j = 0; // 慢指针
for (int i = 0; i < nums.length; i++) { // i为快指针,用于迭代
if (nums[j] != nums[i]) {
j++;
nums[j] = nums[i];
}
}
return j + 1;
}

2.4 移动零

题目(原题见Leetcode)

1
2
3
4
5
6
7
8
9
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:

1. 必须在原数组上操作,不能拷贝额外的数组。
2. 尽量减少操作次数。

该题解决有非常多种思路,例如我们用比较简单的方法:先将数组中不为0的元素全部移动到最前边,最后再在最后边填充zeroNum - 1个零元素:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void moveZeroes1(int[] nums) {
int zeroNum = 0;

/* 将不为零的元素移动到数组的最前边 */
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
nums[zeroNum] = nums[i];
zeroNum++;
}
}
/* 填充零元素 */
while (zeroNum < nums.length) {
nums[zeroNum] = 0;
zeroNum++;
}
}

但是该题最后的方法来是通过双指针来实现,但是比较不同的是:慢指针和快指针都是由后往前移动,快指针依然用于迭代,判断迭代到的元素是否等于零,如果为0,通过快指针和慢指针的差值将部分元素前移。慢指针用于指向下一个添加0元素的下标 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void moveZeroes(int[] nums) {
int curIndex = nums.length - 1; // 快指针
int lastIndex = nums.length - 1; // 慢指针
int count;

while (curIndex >= 0) {
if (nums[curIndex] == 0) {
count = lastIndex - curIndex;
/* 根据lastIndex与curIndex之间的差值,将元素前移 */
for (int i = 0; i < count; i++) {
nums[curIndex + i] = nums[curIndex + i + 1];
}
/* 然后再将零放在最后的所有的零最前的一个位置,即慢指针lastIndex指向的位置 */
nums[lastIndex] = 0;
lastIndex--;
}
curIndex--;
}
}
Pushy wechat
欢迎订阅我的微信公众号