阅读量:2
目录
前言
双指针
常见的双指针有两种形式，一种是对撞指针，⼀种是左右指针。
对撞指针：一般用于顺序结构中，也称左右指针。
- 对撞指针从两端向中间移动。一个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼近。
- 对撞指针的终止条件一般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：
- left == right （两个指针指向同一个位置）
- left > right （两个指针错开）
快慢指针：又称为龟兔赛跑算法，其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。
这种方法对于处理环形链表或数组非常有用。
其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使用快慢指针的思想。
快慢指针的实现方式有很多种，最常用的⼀种就是：
- 在一次循环中，每次让慢的指针向后移动一位，而快的指针往后移动两位，实现一快一慢。
1. 三数之和
题目描述：
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[ ]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
提示：
3 <= nums.length <= 3000
-105 <= nums[i] <= 105
2. 解法（排序+双指针）：
算法思路：
本题与两数之和类似，是非常经典的面试题。
与两数之和稍微不同的是，题目中要求找到所有「不重复」的三元组。那我们可以利用在两数之和那里用的双指针思想，来对我们的暴力枚举做优化：
- 先排序；
- 然后固定⼀个数 a ：
- 在这个数后面的区间内，使用「双指针算法」快速找到两个数之和等于 -a 即可。
但是要注意的是，这道题里面需要有「去重」操作~
- 找到⼀个结果之后， left 和 right 指针要「跳过重复」的元素；
- 当使用完⼀次双指针算法之后，固定的 a 也要「跳过重复」的元素
算法流程：
先将 nums 排序，时间复杂度为 O(NlogN)。
固定 333 个指针中最左（最小）元素的指针 k，双指针 i，j 分设在数组索引 (k,len(nums))(k, len(nums))(k,len(nums)) 两端。
双指针 iii , jjj 交替向中间移动，记录对于每个固定指针 k 的所有满足 nums[k] + nums[i] + nums[j] == 0 的 i,j 组合：
- 当
nums[k] > 0时直接break跳出：因为nums[j] >= nums[i] >= nums[k] > 0，即 3 个元素都大于 0 ，在此固定指针 k 之后不可能再找到结果了。 - 当
k > 0且nums[k] == nums[k - 1]时即跳过此元素nums[k]：因为已经将nums[k - 1]的所有组合加入到结果中，本次双指针搜索只会得到重复组合。
3.i，j分设在数组索引 (k,len(nums))两端，当i < j时循环计算sum = nums[k] + nums[i] + nums[j]，并按照以下规则执行双指针移动：
当
s < 0时，i += 1并跳过所有重复的nums[i]；当
s > 0时，j -= 1并跳过所有重复的nums[j]；当
s == 0时，记录组合[k, i, j]至res，执行i += 1和j -= 1并跳过所有重复的nums[i]和nums[j]，防止记录到重复组合。
C++代码：
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> ret; // 1. 排序 sort(nums.begin(), nums.end()); // 2. 利⽤双指针解决问题 int n = nums.size(); for (int i = 0; i < n;) // 固定数 a { 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) right--; else if (sum < target) left++; else { ret.push_back({nums[i], nums[left], nums[right]}); left++, right--; // 去重操作 left 和 right while (left < right && nums[left] == nums[left - 1]) left++; while (left < right && nums[right] == nums[right + 1]) right--; } } // 去重 i i++; while (i < n && nums[i] == nums[i - 1]) i++; } return ret; } }; 
Java代码：
class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> ret = new ArrayList<>(); // 1. 排序 Arrays.sort(nums); // 2. 利⽤双指针解决问题 int n = nums.length; for (int i = 0; i < n; ) // 固定数 a { 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) right--; else if (sum < target) left++; else { // nums[i] nums[left] num[right] ret.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[left], nums[right]))); left++; right--; // 缩⼩区间继续寻找 // 去重：left right while (left < right && nums[left] == nums[left - 1]) left++; while (left < right && nums[right] == nums[right + 1]) right--; } } // 去重：i i++; while (i < n && nums[i] == nums[i - 1]) i++; } return ret; } } 
3. 四数之和（medium）
题目描述：
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件
且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为
两个四元组重复）：
- 0 <= a, b, c, d < n
- a、b、c 和 d 互不相同
- nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
提示：
1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109
4. 解法（排序 + 双指针）
前置题目:
请先完成三数之和。
思路:
思路和三数之和 一样，排序后，枚举 nums[a]作为第一个数，枚举 nums[b] 作为第二个数，那么问题变成找到另外两个数，使得这四个数的和等于 target，这可以用双指针解决。
对于 nums[a] 的枚举：
设 s=nums[a]+nums[a+1]+nums[a+2]+nums[a+3]。如果 s>targets，由于数组已经排序，后面无论怎么选，选出的四个数的和不会比 s 还小，所以后面不会找到等于 target的四数之和了。所以只要 s>targets ，就可以直接 break 外层循环了。
设 s=nums[a]+nums[n−3]+nums[n−2]+nums[n−1]。如果 s<targets ，由于数组已经排序，nums[a]加上后面任意三个数都不会超过 s，所以无法在后面找到另外三个数与 nums[a]相加等于 target。但是后面还有更大的 nums[a]，可能出现四数之和等于 target 的情况，所以还需要继续枚举，continue 外层循环。
如果 a>0且 nums[a]=nums[a−1]，那么 nums[a] 和后面数字相加的结果，必然在之前算出过，所以无需执行后续代码，直接 continue 外层循环。（可以放在循环开头判断。）
对于 nums[b] 的枚举（b 从 a+1 开始），也同样有类似优化：
设 s=nums[a]+nums[b]+nums[b+1]+nums[b+2]。如果 s>targets，由于数组已经排序，后面无论怎么选，选出的四个数的和不会比 s 还小，所以后面不会找到等于 target 的四数之和了。所以只要 s>targets ，就可以直接 break。
设 s=nums[a]+nums[b]+nums[n−2]+nums[n−1]。如果 s<targets，由于数组已经排序，nums[a]+nums[b] 加上后面任意两个数都不会超过 s，所以无法在后面找到另外两个数与 nums[a] 和 nums[b] 相加等于 target。但是后面还有更大的 nums[b]，可能出现四数之和等于 target 的情况，所以还需要继续枚举，continue。
如果 b>a+1b>a+1b>a+1 且 nums[b]=nums[b−1]，那么 nums[b]\textit{nums}[b]nums[b] 和后面数字相加的结果，必然在之前算出过，所以无需执行后续代码，直接 continue。注意这里 b>a+1 的判断是必须的，如果不判断，对于示例 2 这样的数据，会直接 continue，漏掉符合要求的答案。
对于 Java/C++ 等语言，注意相加结果可能会超过 32 位整数范围，需要用 64 位整数存储四数之和。
思路来自灵茶山艾府
C++代码：
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> ret; // 1. 排序 sort(nums.begin(), nums.end()); // 2. 利⽤双指针解决问题 int n = nums.size(); for (int i = 0; i < n; ) // 固定数 a { // 利⽤ 三数之和 for (int j = i + 1; j < n; ) // 固定数 b { // 双指针 int left = j + 1, right = n - 1; long long aim = (long long)target - nums[i] - nums[j]; while (left < right) { int sum = nums[left] + nums[right]; if (sum < aim) left++; else if (sum > aim) right--; else { ret.push_back({ nums[i], nums[j], nums[left++], nums[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 ret; } }; 
Java代码：
class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> ret = new ArrayList<>(); // 1. 排序 Arrays.sort(nums); // 2. 利⽤双指针解决问题 int n = nums.length; for (int i = 0; i < n; ) // 固定数 a { // 三数之和 for (int j = i + 1; j < n; ) // 固定数 b { // 双指针 int left = j + 1, right = n - 1; long aim = (long)target - nums[i] - nums[j]; while (left < right) { int sum = nums[left] + nums[right]; if (sum > aim) right--; else if (sum < aim) left++; else { ret.add(Arrays.asList(nums[i], nums[j], nums[left++], nums[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 ret; } } 
