LeetCode 热题 100-双指针
分析
一个指针逐个遍历元素，如果它所指的元素是0，就定义一个新的指针，不断后移直到其所指不为0，交换两指针元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size();
for(int i = 0; i < n; i++){
if(nums[i] == 0){
int j = i + 1;
while(j < n && nums[j] == 0) j++;
if(j < n){
swap(nums[i], nums[j]);
}else{
break;
}
}
}
}
};
|
- 时间复杂度：$O(n^2)$，在最坏情况下（比如数组中大部分元素都是0），对于每个 i，都可能需要遍历到数组末尾。
- 空间复杂度：O(1)
双指针
使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。
右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。
因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size();
int left = 0, right = 0;
while(right < n){
if(nums[right] != 0){
swap(nums[left], nums[right]);
left++;
}
right++;
}
}
};
|
双指针
找到(j - i ) * min(height[i], height[j])的最大值。左指针指向最左边，右指针指向最右边，这样就可以保证每次移动时(j-i)一定是减小的，每次移动较低的那个指针。
如果移动高的那一边，会有两种情况：
1、下一根柱子的高度比现在高，高度还取最小值低的那边，最大水量比原来小
2、下一根柱子的高度比现在低，高度比原来的最小值还小，最大水量比原来小
如果移动低的那一边，会有两种情况：
1、下一根柱子的高度比现在高，高度就可以取更高的值，最大水量不一定比原来小
2、下一根柱子的高度比现在低，高度比原来的最小值还小，最大水量比原来小
所以应该移动低的那一边。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int maxArea(vector<int>& height) {
int n = height.size();
int left = 0, right = n-1;
int ans = 0;
while(left < right){
int cur = (right - left) * min(height[left], height[right]);
ans = max(ans, cur);
if(height[left] < height[right]){
left++;
}else{
right--;
}
}
return ans;
}
};
|
双指针
- 首先对数组进行排序；
- 跳过相等的数字，固定一个数字，此时转化为寻找两数之和等于
0-nums[i]的问题；
- 定义左右指针，分别指向
i+1和n-1；
- 左右指针都需要跳过重复元素，因为题目要求不能包含重复的三元组。
- 如果当前两数之和等于target，将当前组合加入结果集，否则如果大于target，右指针左移，否则左指针右移。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
for(int i = 0; i < n - 2; i++){
if(i > 0 && nums[i] == nums[i-1]) continue;
int target = 0 - nums[i];
int left = i + 1, right = n - 1;
while(left < right){
int sum = nums[left] + nums[right];
if(sum == target){
ans.push_back({nums[i], nums[left], nums[right]});
for(left += 1; left < right && nums[left] == nums[left-1]; left++);
for(right -= 1; right > left && nums[right] == nums[right+1]; right--);
}else if(sum > target){
right--;
}else{
left++;
}
}
}
return ans;
}
};
|
- 时间复杂度：$O(n^2)$
- 空间复杂度：O(logn)，忽略存储答案的空间，额外的排序的空间复杂度为 O(logN)。
双指针
用前后缀去思考，即当前这个位置能接的水的量，取决于前后缀最大值中的较小值，以及当前柱子的高度。因此可以用两个数组去保存每个位置的前缀最大值和后缀最大值，但空间可以进一步优化，即两指针分别从左右两端出发，如果前缀最大值比后缀最大值小，那么更新前面的木桶，即ans += preMax - height[left]，否则更新后面的木桶，即ans += sufMax - height[right]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int left = 0, right = n - 1;
int preMax = 0, sufMax = 0;
int ans = 0;
while(left < right){
preMax = max(preMax, height[left]);
sufMax = max(sufMax, height[right]);
if(preMax < sufMax){
ans += preMax - height[left];
left++;
}else{
ans += sufMax - height[right];
right--;
}
}
return ans;
}
};
|
这道题还有单调栈的做法，之前做过，但是现在又不记得了，明天把单调栈专题的部分好好学习一下。
总结
hot100中双指针的题目之前全都做过，但是现在又不记得了，前面几道题自己思考或者看过提示之后还能写出来，接雨水这道题也有印象是和前后缀有关，但是无法形成具体的思路。要多加复习！