一、复写0

题目：

注意：题目要求是原数组上复写

思路：
一、确定最后一个复写的位置。定义两个变量cur等于0，dest等于-1，让cur去遍历数组。如果cur指向的元素是0，dest往后两步，非0，往后一步。判断dest的位置，如果大于等于n-1，就停止操作，否则cur++

1. 根据cur指向的元素dest跳一步还是两步
2. dest移动操作
3. 判断dest的位置，如果是大于等于n-1就跳出后面的操作
4. cur++

二、细节处理。有可能dest走到了n的位置，说明cur遇到了0，0多出来了一个，dest就要往前移动两步，cur往前移动一步，并且n-1即最后一个元素变成0

三、复写。cur指向的元素是0，dest指向的元素覆盖成0，dest往前移动一步，然后此时这个位置再覆盖成0，dest往前一步，cur往前一步；cur指向的元素不是0，dest指向的元素覆盖成0，dest往前移动一步，cur往前一步。

代码：

class Solution {
public:void duplicateZeros(vector<int>& arr) {int n = arr.size();int cur = 0, dest = -1;// 确定最后一个复写的位置while (dest != n - 1){if (arr[cur] == 0){dest += 2;if (dest >= n - 1) break;}else{dest++;if (dest >= n - 1) break;}cur++;}// 细节处理if (dest == n){arr[n - 1] = 0;dest -= 2;cur--;}// 复写操作while (cur >= 0){if (arr[cur] == 0){arr[dest--] = arr[cur];arr[dest--] = arr[cur--];}else{arr[dest--] = arr[cur--];}}}
};

二、三数之和

题目：

思路：
先排序，固定一个数，剩下的操作是两数之和。目标数是0-固定的数。注意去重。遇到合法的数放入ret，然后还要去重。

代码：

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ret;// 排序sort(nums.begin(), nums.end());int n = nums.size();for (int i = 0; i < n; 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){if (nums[left] + nums[right] > target){right--;}else if (nums[left] + nums[right] < target){left++;}else{ret.push_back({ nums[i], nums[left], nums[right] });right--;left++;// 去重while (left < right && nums[right] == nums[right + 1])--right;while (left < right && nums[left] == nums[left - 1])++left;}}}return ret;}
};

三、四数之和

题目：

注意：不重复，数据范围

思路：同三数之和，多一层循环固定数，目标数是变量。排序、去重、不漏。

代码：

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> ret;// 排序sort(nums.begin(), nums.end());int n = nums.size();// a+b+c+d=target => a+b+c=target-d => a+b = target-d-cfor (int i = 0; i < n; i++){if (i > 0 && nums[i] == nums[i - 1]) continue;// 去重long long k = target - nums[i];for (int j = i + 1; j < n; j++){if (j > i + 1 && nums[j] == nums[j - 1]) continue;// 去重long long tmp = k - nums[j];// 两数之和int left = j + 1, right = n - 1;while (left < right) // 不漏{if (nums[left] + nums[right] > tmp){right--;}else if (nums[left] + nums[right] < tmp){left++;}else{ret.push_back({ nums[i], nums[j], nums[left], nums[right] });right--;while (left < right && nums[right] == nums[right + 1])// 去重right--;left++;while (left < right && nums[left] == nums[left - 1])// 去重left++;}}}}return ret;}
};