【优先算法】双指针

✨✨欢迎大家来到Celia的博客✨✨

🎉🎉创作不易，请点赞关注，多多支持哦🎉🎉

所属专栏：优先算法

个人主页：Celia's blog~

移动零

复写零

快乐数

盛水最多的容器

有效三角形个数

查找价值为目标值的两个商品

三数之和

四数之和

移动零

通过维护两个指针将数组分为三个部分：

非零
全零
未处理。

保证各个区间的要求不变：

cur指向的值为0， cur++
cur指向的值不为0，由于des本身的位置的值不为0，所以先要des++，再交换两个位置的值。
cur++，移动到下一个位置，以保证区间特点要求。

class Solution {
public:void moveZeroes(vector<int>& nums){int cur = 0, prev = -1;while(cur < nums.size()){if(nums[cur]){prev++;swap(nums[prev], nums[cur]);cur++;}else{cur++;}}    }
};

复写零

需要先模拟遍历，确定从哪一个位置开始复写（有特殊情况需要额外处理）。再从后向前遍历，进行复写。

class Solution {
public:void duplicateZeros(vector<int>& arr){int cur = 0, prev = -1;int n = arr.size();while(cur < n){if(arr[cur]) prev++;else prev += 2;if(prev >= n - 1) break;cur++;}if(prev >= n){arr[n - 1] = 0;prev -= 2;cur -= 1;}while(cur >= 0){if(arr[cur]) arr[prev--] = arr[cur--];else {arr[prev--] = 0;arr[prev--] = 0;cur--;}}}
};

快乐数

把数字变化的过程抽象两种成环链表：

环中全为1
环中不是1

用一次计算来模拟链表的一次向后遍历，使用快慢指针来找到相交节点，并判断该节点的值。

class Solution {
public:int change(int num){int tmp = 0;while(num){int x = num % 10;tmp += x * x;num /= 10;}return tmp;}bool isHappy(int n) {int low = n, fast = change(n);while(low != fast){low = change(low);fast = change(fast);fast = change(fast);}if(low == 1) return true;return false;}
};

盛水最多的容器

先定位最左最右节点。

若r向左移动：

长度一定减小
若是遇到比r节点高的，高度不变（由于取最小）。
若是遇到比r节点小的，高度减小（由于取最小）。
所以r，l中小的那一个无论怎么移动，总体积都在减小。没有必要继续遍历。
故只要移动l，r中最小的那一个，就可以不断尝试其他的结果。

class Solution {
public:int maxArea(vector<int>& height){int l = 0, r = height.size() - 1;int maxV = 0;while(l < r){int V = min(height[l], height[r]) * (r - l);if(V > maxV) maxV = V;if(height[l] < height[r]) l++;else r--;}return maxV;}
};

有效三角形个数

判断三角形的方法：

两边之和大于第三边，判断三次
有序：判断一次

故选择有序的情况进行三角形判断。先对数组进行排序，取一个最大的边（最后一个数组元素开始，依次向后移动）。再定义l，r分别在0位置和max-1位置处。

若是l和r的和大于max，由于数组有序，l之后的元素必然都符合要求，共有r-l个结果。此时r的所有情况统计完毕，将r向左移动一位。
若是l和r的和小于max，由于数组有序，l之后的元素必然都不符合要求，无结果。此时l的所有情况统计完毕，将l向右移动一位。
当l >= r时，一轮遍历结束，将max向左移动一位，继续上述操作。

class Solution {
public:int triangleNumber(vector<int>& nums){sort(nums.begin(), nums.end());int max = nums.size() - 1;int count = 0;while(max >= 2){int l = 0, r = max - 1;while(l < r){if(nums[l] + nums[r] > nums[max]) count += r - l, r--;else l++;}max--;}return count;}
};

查找价值为目标值的两个商品

利用数组有序的特点，用两个指针快速遍历数组，找到结果后立即返回即可。

l和r的和小于目标值：l和最大的元素相加小于目标值，那么当前l右边的值都必然不符合要求，l++。
l和r的和大于目标值：r和最小的元素相加大于目标值，那么当前r左边的值都必然不符合要求，r--。

class Solution {
public:vector<int> twoSum(vector<int>& price, int target){int l = 0,r = price.size() - 1;while(l < r){if(price[l] + price[r] > target) r--;else if(price[l] + price[r] < target) l++;else break;}return {price[l], price[r]};}
};

三数之和

与上一题思路大致相同，但必须保证数组有序，故需要先排序。
并且这道题需要例出所有情况，不能找到马上返回，需要继续遍历。
所有的情况不能有重复，所以移动所有指针时需要跳过重复的元素。

此题相比两个数多了一个数：

先固定一个数
再将剩余的两个数，用“两个数的和”这道题的方法来做（双指针）。
之后大体框架相同，需要注意一些细节（越界问题、去重、不漏可能情况）。

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums){sort(nums.begin(), nums.end());vector<vector<int>> vv;int cur = 0;while(cur < nums.size() - 2){int l = cur + 1, r = nums.size() - 1;while(l < r){int tmp = nums[l] + nums[r] + nums[cur];if(!tmp){vv.push_back({nums[l], nums[r],  nums[cur]});r--, l++;while(l < r && r >= 0 && nums[r] == nums[r + 1]){r--;}while(l < r && l < nums.size() && nums[l] == nums[l - 1]){l++;}}else if(tmp > 0){r--;while(l < r && r >= 0 && nums[r] == nums[r + 1]){r--;}}else{l++;while(l < r &&(l < nums.size() && nums[l] == nums[l - 1])){l++;}}}cur++;while(cur < nums.size() && nums[cur] == nums[cur - 1]){cur++;}}return vv;}
};

四数之和

此题在三个数的基础上多了一个数：

固定两个数
剩下两个数按照双指针思路来做，大体框架一模一样。

此题需要注意数组元素的大小容易过大，导致计算溢出，所以需要采用两两相加的方式来比较大小。

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target){vector<vector<int>> vv;int n = nums.size();sort(nums.begin(), nums.end());int a = 0;while(a < n - 3){int b = a + 1;while(b < n - 2){int l = b + 1, r = n - 1;long long aim = (long long)target -  nums[a] - nums[b];while(l < r){long long sum = nums[l] + nums[r];if(sum == aim){vv.push_back({nums[a], nums[b], nums[l], nums[r]});l++, r--;while(l < r && nums[l] == nums[l - 1]) l++;while(l < r && nums[r] == nums[r + 1]) r--;}else if(sum < aim) l++;else r--;}b++;while(b < n - 2 && nums[b] == nums[b - 1]) b++;}a++;while(a < n - 3 && nums[a] == nums[a - 1]) a++;}return vv;}
};