1.移动零
283. 移动零 - 力扣（LeetCode）
双指针算法
两个指针的作用：
cur：从左向右遍历数组 dest：已处理区间内非零元素的最后一个位置。
[0,dest] 非零元素
[dest+1,cur] 0
[cur,n-1] 待处理
cur遍历过程中遇到0元素cur++，遇到非0元素交换cur和dest+1位置的值，dest++和cur++
void moveZeroes(vector<int>& nums) {for(int cur = 0, dest = -1; cur < nums.size(); cur++){if(nums[cur]){swap(nums[cur],nums[dest + 1]);dest++;}} }2.复写零
1089. 复写零 - 力扣（LeetCode）
方法一：运用库函数
直接遍历数组，在0的位置之前插入0，最后resize为原空间大小
class Solution {
public:void duplicateZeros(vector<int>& arr) {int n = arr.size();auto it = arr.begin();while(it != arr.end()){if(*it == 0){it = arr.insert(it,0);it++;}it++;} arr.resize(n); }
};方法二：双指针法
1.先找到最后一个复写的数
先判断cur位置的值，再决定dest往后移动一不还是两步，判断dest是否已经到了结束位置，cur++。
找到最后一个复写的树，处理一下边界情况，如果dest == n 将arr[dest - 1]的位置置为0，cur--，dest -= 2。
2.从后往前完成复写操作
void duplicateZeros(vector<int>& arr) {int dest = -1,cur = 0;int n = arr.size();while (cur < n){if(arr[cur] == 0){dest += 2;}else{dest++;}if(dest >= n - 1)break;cur++;}if(dest == n){arr[dest - 1] = 0;cur--;dest -= 2;}while(cur >= 0){if(arr[cur]){arr[dest--] = arr[cur--];}else{arr[dest--] = 0;arr[dest--] = 0;cur--;}}}3.快乐数
202. 快乐数 - 力扣（LeetCode）
思路：上述情况所示，这个值最后会形成一个环，一个环中全为1，一个环中没有1。所以可以使用判断链表是否有环的解法：快慢双指针。
1.定义快慢双指针
2.慢指针每次向后移动一位，快指针每次向后移动两步
3.判断相遇时候的值就可以
class Solution {
public:int retn(int n){int ret = 0;while(n){int x = n % 10;n /= 10;ret += x*x;}return ret;}bool isHappy(int n) {int slow = n;int fast = retn(n);while(slow != fast){slow = retn(slow);fast = retn(retn(fast));}return slow == 1;}
};4.盛最多水的容器
11. 盛最多水的容器 - 力扣（LeetCode）
方法一（未通过）：暴力解法，直接遍历数组
class Solution
{
public:int maxArea(vector<int>& height) {int max = 0;for(int i = 0; i < height.size(); i++){for(int j = i + 1; j < height.size();j++){int m = min(height[i],height[j]);int ret = m * (j - i);if(max < ret)max = ret;}}return max;}
};但是数据太多会超时。
方法二：利用单调性，双指针算法
class Solution
{
public:int maxArea(vector<int>& height){int left = 0,right = height.size() - 1, ret = 0;while(left < right){int v = min(height[left],height[right]) * (right - left);ret = max(ret,v);if(height[left] < height[right])left++;elseright--;}return ret;}};5.有效三角形的个数
611. 有效三角形的个数 - 力扣（LeetCode）
思路：先对数组排序（在有序中只要判断a+b>c就可以判断是否为三角形），利用单调性，用双指针算法来解决问题
- 先找最大的数就是排序完的最后一个数
- 在最大数的左区间，使用双指针算法，快速统计出符合要求的三元组的个数
- 当nums[left] + nums[right] > nums[c] 剩下left的右边的数与right的数相加必然大于c的数，ret直接加等right - left区间的数，right再--。
- 当nums[left] + nums[right] < nums[c] left与right左边的数相加肯定小于c的数，直接++left
- 结束条件是c的位置要大于等于2（c左边还有right和left）
class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());int c = nums.size() - 1;int left = 0, right = c - 1;int ret = 0;while(c >= 2){while(left < right){if(nums[left] + nums[right] > nums[c]){ret += right - left;right--;}else{left++;}}c--;right = c - 1;left = 0;}return ret;}
};6.查找总价格为目标的两个商品
LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）
思路：利用单调性（题目中说了有序），使用双指针算法解决问题
定义left指向开始，和right指向结尾，判断两数相加的值与target的关系，大于就right--，小于left++
vector<int> twoSum(vector<int>& price, int target) {vector<int> ret;int left = 0, right = price.size() - 1;while(left < right){if(price[left] + price[right] == target){ret.push_back(price[left]);ret.push_back(price[right]);break;}else if(price[left] + price[right] > target){--right;}else{++left;}} return ret;}还有一种直接隐式类型转换做返回值
vector<int> twoSum(vector<int>& price, int target) { int left = 0, right = price.size() - 1;while(left < right){int sum = price[left] + price[right];if(sum > target) right--;else if(sum < target) left++;else return {price[left],price[right]};}//不加这句在leetcode上编译不过，所以要返回一个值return {-1,-1}; }7.三数之和
思路：对数组进行排序后，使用双指针，固定一个数c，然后利用上面两个商品的两数求和来求c的相反数，区别是找到一种结果后不要停（当c大于0时，因为数组有序，所以在c右边不可能找到相加为c相反数的值）。
这道题还需要去重，找到一种结果后，left和right要跳过重复元素，当使用完一次双指针后c也要跳过重复元素。
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(),nums.end());vector<vector<int>> vv;for(int c = 0; c < nums.size() - 2; c++){if(nums[c] > 0)//大于0后，后面的数相加绝对不会等于他的相反数break;int left = c + 1;int right = nums.size() - 1;while(left < right){int x = -nums[c];int sum = nums[left] + nums[right];vector<int> v;if(sum < x)left++;else if(sum > x)right--;else{v.push_back(nums[left]);v.push_back(nums[right]);v.push_back(nums[c]);vv.push_back(v);while(left < right && nums[left] == nums[left + 1]){left++;}while(right > left &&nums[right] == nums[right - 1]){right--;}left++;right--;}while(nums[c] == nums[c + 1] && c < nums.size() - 2)c++;}}return vv;}
};8.四数之和
18. 四数之和 - 力扣（LeetCode）
和上面三数之和的思路一样，四数之和是固定两个数，再左右指针往下走，但是这个题在减的时候会报错，所以要开成long long。
class Solution
{
public:
vector<vector<int>> fourSum(vector<int>& nums, int target)
{sort(nums.begin(),nums.end());vector<vector<int>> vv;size_t n = nums.size();for(size_t i = 0; i < n; ){for(size_t j = i + 1; j < n;){size_t left = j + 1;size_t right = n - 1;long long x = (long long)target - nums[i] - nums[j];while(left < right){int sum = nums[left] + nums[right];if(sum < x){left++;}else if(sum > x){right--;}else{vector<int> v;v.push_back(nums[i]);v.push_back(nums[j]);v.push_back(nums[left]);v.push_back(nums[right]);vv.push_back(v);left++;right--;while(left < right && nums[left] == nums[left - 1]){left++;}while(left < right && nums[right] == nums[right + 1]){right--;}}}j++;while(j < n && nums[j] == nums[j - 1]){j++;}}i++;while(i < n && nums[i] == nums[i - 1]){i++;}}return vv;
}
};