专题一：双指针【优选算法】

双指针应用场景：

数组划分、数组分块

 

目录

 

一、移动0

 二、复写0 从后向前

  三、快乐数 链表带环

 四、盛水最多的容器 单调性+双指针

五、有效三角形个数 单调性+双指针

 六、和为s的两个数字

七、三数之和 细节多 需再练

---

一、移动0

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

 二、复写0 从后向前

c

细节：当最后cur = 0时，要小心越界。

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

  三、快乐数 链表带环

class Solution {
public:int bitSum(int n){int ret = 0;while(n>0){ret += (n%10)*(n%10);n /= 10;}return ret;}bool isHappy(int n) {int slow = n, fast = bitSum(n);while(slow != fast){slow = bitSum(slow);fast = bitSum(bitSum(fast));}return slow == 1;}
};

 四、盛水最多的容器 单调性+双指针

注意：高度由矮的决定。

class Solution {
public:int maxArea(vector<int>& height) {int n = height.size();int left = 0,right = n-1;int ret = 0;while(left < right){int v = min(height[left],height[right])*(right-left);ret = max(ret,v);if(height[left] < height[right]) left++;else right--;}return ret;}
};

五、有效三角形个数 单调性+双指针

核心：两小边之和大于第三边就可以组成三角形。

 

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

 六、和为s的两个数字

出现上面这样的报错是因为编译器觉得可能没有返回值，最后随便返回一个就行。 

七、三数之和 细节多 需再练

注意：要避免越界。 

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {int n = nums.size();sort(nums.begin(),nums.end());vector<vector<int>> ret;int i = 0;while(i < n){if(nums[i] > 0)break;int left = i+1,right = n-1,target = -nums[i];while(left < right){int sum = nums[left]+nums[right];if(sum < target) left++;else if(sum > target) right--;else {ret.push_back({nums[i],nums[left],nums[right]});left++,right--;while(left < right && nums[left] == nums[left-1]) left++;while(left < right && nums[right] == nums[right+1]) right--;} }i++;while(i < n && nums[i] == nums[i-1]) i++;}return ret;}
};