一、双指针之左右指针相关题目
1.1 题目要求：给定一个升序排列的整数数组，找到两个数，使它们的和等于给定的数，有且仅有一个满足条件的解，返回索引。
- 题目分析：需要两个指针，一个指向开头，一个指向末尾，然后向中间遍历，如果指向的两个数相加正好等于target的话，直接返回两个指针的位置即可，若小于target，左指针右移一位，若大于target，右指针左移一位，以此类推直至两个指针相遇停止。
- 题目解答：
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
vector<int> res(2, -1);
int left = 0, right = numbers.size() - 1;
while(left < right){
int temp = numbers[left] + numbers[right];
if(temp > target){
right--;
}else if(temp < target){
left++;
}else{
res[0] = left + 1;
res[1] = right + 1;
return res;
}
}
return res;
}
};
1.2 题目要求：给定n个整数的数组nums，nums中是否有元素a，b，c，满足a + b + c = 0？ 找到数组中所有的三元组。注意：解决方案中不得包含重复的三元组。
- 题目分析：尝试把三数和问题转化为两数和问题：同样先对数组排序，设置三个指针i,left,right，i指针指向第一个数x，则left,right要指向数组中剩余数中的两个，并且指向的两数和为-x，从而转化为两数和问题。
- 题目解答：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
int n = nums.size();
if(n <= 2) return res;
sort(nums.begin(), nums.end());
for(int i = 0; i < n-2; i++){
int left = i + 1, right = n - 1;
while(left < right){
int temp = nums[left] + nums[right];
if(temp > -nums[i]){
right--;
}else if(temp < -nums[i]){
left++;
}else{
vector<int> tmp{nums[i], nums[left], nums[right]};
res.push_back(tmp);
left++;
right--;
while(left < right && nums[left] == nums[left - 1]) left++;
while(left < right && nums[right] == nums[right + 1]) right--;
}
}
while(i + 1 < n -2 && nums[i] == nums[i + 1]) i++;
}
return res;
}
};
1.3 题目要求：这道题让我们求最接近给定值的三数之和。
- 题目分析：在上一道的Sum基础上又增加了些许难度，那么这道题让我们返回这个最接近于给定值的值，即我们要保证当前三数和跟给定值之间的差的绝对值最小，所以我们需要定义一个变量small用来记录差的绝对值。
- 题目解答：
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int n = nums.size(), res = INT_MIN, small = INT_MAX;
sort(nums.begin(), nums.end());
for(int i = 0; i < n-2; i++){
int left = i + 1, right = n - 1;
while(left < right){
int temp = nums[left] + nums[right] + nums[i];
if(abs(temp - target) < small){
res = temp;
small = abs(temp - target);
}
if(temp > target){
right--;
}else if(temp < target){
left++;
}else{
return target;
}
}
while(i + 1 < n -2 && nums[i] == nums[i + 1]) i++;
}
return res;
}
};
1.4 题目要求：给定n个整数的数组nums，nums中是否有元素a，b，c，d 满足a + b + c + d= target？ 找到数组中所有的四元组。注意：解决方案中不得包含重复的四元组。
- 题目分析：在上一道的15. 3Sum基础上又增加了些许难度，尝试把四数和问题转化为两数和问题：同样先对数组排序，设置四个指针k,i,left,right，k指针指向第一个数，i指针指向第二个数,则left,right要指向数组中剩余数中的两个，从而转化为两数和问题。
- 题目解答：
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
int n = nums.size();
if(n <= 3) return res;
sort(nums.begin(), nums.end());
for(int k = 0; k < n-3; k++){
for(int i = k + 1; i < n-2; i++){
int left = i + 1, right = n - 1;
int ret = target - nums[k] - nums[i];
while(left < right){
int temp = nums[left] + nums[right];
if(temp > ret){
right--;
}else if(temp < ret){
left++;
}else{
vector<int> tmp{nums[k], nums[i], nums[left], nums[right]};
res.push_back(tmp);
left++;
right--;
while(left < right && nums[left] == nums[left - 1]) left++;
while(left < right && nums[right] == nums[right + 1]) right--;
}
}
while(i + 1 < n -2 && nums[i] == nums[i + 1]) i++;
}
while(k + 1 < n -3 && nums[k] == nums[k + 1]) k++;
}
return res;
}
};
二、双指针之快慢指针
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slow = 0, fast = 0, n = nums.size();
while(fast < n){
if(nums[fast] != val) nums[slow++] = nums[fast];
fast++;
}
return slow;
}
};
2.1 题目要求：这道题让我们移除一个数组中和给定值相同的数字，并返回新的数组的长度。
- 题目分析：使用slow和fast两个指针，从头部开始遍历，遍历一次fast指针前进一步，当遍历元素不满足指定的值，slow指针前进一步，这样不满足条件的整数都被移动到数组的前面。
- 题目解答
2.2 题目要求：这道题要我们从有序数组中去除重复项。
- 题目分析：这道题的解题思路是，我们使用快慢指针来记录遍历的坐标，最开始时两个指针都指向第2个数字，如果快指针指向的数等于慢指针的前1个数，则快指针向前走一步，如果不同，则两个指针都向前走一步，这样当快指针走完整个数组后，慢指针当前的坐标就是数组中不同数字的个数。
- 题目解答：
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int slow = 1, fast = 1, n = nums.size();
if(n <= 1) return n;
while(fast < n){
if(nums[fast] != nums[slow - 1]) nums[slow++] = nums[fast];
fast++;
}
return slow;
}
};
2.3 题目要求：这道题要我们从有序数组中去除重复项，每个数最多重复出现2次。
- 题目分析：与上一道解题思路相似，我们使用快慢指针来记录遍历的坐标，最开始时两个指针都指向第3个数字，如果快指针指向的数等于慢指针的前2个数，则快指针向前走一步，如果不同，则两个指针都向前走一步，这样当快指针走完整个数组后，慢指针当前的坐标就是数组中不同数字的个数。
- 题目解答：
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int slow = 2, fast = 2, n = nums.size();
if(n <= 2) return n;
while(fast < n){
if(nums[fast] != nums[slow - 2]) nums[slow++] = nums[fast];
fast++;
}
return slow;
}
};
三、双指针之后序指针相关题目：
3.1题目要求：给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1中，使得 num1 成为一个有序数组。你可以假设 nums1有足够的空间（空间大小大于或等于m + n）来保存 nums2 中的元素。在 nums1 和 nums2 中初始化的元素的数量分别是 m 和 n。
- 题目分析：算法思想是：由于合并后A数组的大小必定是m+n，所以从最后面开始往前赋值，先比较A和B中最后一个元素的大小，把较大的那个插入到m+n-1的位置上，再依次向前推。如果A中所有的元素都比B小，那么前m个还是A原来的内容，没有改变。如果A中的数组比B大的，当A循环完了，B中还有元素没加入A，直接用个循环把B中所有的元素覆盖到A剩下的位置。
- 题目解答：
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i = m - 1, j = n - 1, k = m + n -1;
while(i >= 0 && j >= 0){
if(nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
else nums1[k--] = nums2[j--];
}
while(j >= 0) nums1[k--] = nums2[j--];
}
};
