15. 三数之和
15. 三数之和
分析
有 1. 两数之和 的前车之鉴，我一开始就想到用哈希法，有两种方案，
- 一种是两层 for 循环，在里面那层 for 循环中使用 Hash，那就是用 for+for+hash 的方式来实现 3 个 for 循环嵌套的效果。
- 另一种方案是，先用两层 for 循环，把 nums 中两两相加的结果放到 Hashmap 里（这是 454. 四数相加 II 给我的灵感），然后再额外用一个 for 循环遍历 nums，检查
target-当前元素是否在 HashMap 中存在，
这两种方案都行，但是得考虑去重，这个去重，有两层意思，
- 首先组合中的元素的索引不能重复，即，一个组合里面，同一个下标不能出现两次，这个其实也不难。
- 然后是结果不能重复，关键是，nums 中的元素本身是可以重复的，也就是说可能存在：组合中的元素的下标有一个不一样，但是呈现出来的组合一模一样，这也需要去重
这个不是不能做，但是写起来太复杂，而且官方解法推荐的也不是这种方案，而是双指针法，那我们就主要研究双指针法。
像这种从一个数组中找出几个元素进行组合，而且元素不能重复的题目，只能先排序然后用三个指针来遍历所有元素了，同时排除相邻元素相等的可能。只能这样做
思路很简单，首先对数组进行排序，排序是为了方便检查重复组合，然后用 for 循环遍历所有元素，遍历的时候指向的元素为第一个元素，假设索引为 i，那么此时将 i+1 定义为 left 指针，为第二个元素，right 指针指向 nums 数组的最后一个元素，为第三个元素，i 固定，我们需要相向移动 left 和 right，来查找 nums[i]+nums[left]+nums[right] 和为 target 的所有组合，循环的执行条件是 left < right（不能相等，相等就重复了），如果小了，就像右移动 left，如果大了，就向左移动 right，如果和为 target，则记录元素组合，并同时移动 left 和 right。
然后就是这道题的重点，就是如何对重复组合去重，因为我们会对 nums 进行了排序，所以 nums 中的所有的重复元素都会放到一起，此时我们只需要对比指针跟其上一个位置的值是否相等即可，如果相等就跳过，就可以避免搜索出重复的三元组合。
- i 的去重，当 i>0 的时候，比较
nums[i]跟nums[i-1]是否相等，如果相等则跳过 - left 的去重，当
left>i+1的时候，比较nums[left]跟nums[left-1]是否相等，如果相等则跳过 - right 的去重，当
right<nums.length-1的时候，比较nums[right]跟nums[right+1]是否相等，如果相等则跳过
小优化
因为 target 值是 0，所以如果第一个元素 nums[i] 就大于 0，那么后面的元素肯定都大于 0，那三数之和就永远不可能为 0，所以这个时候可以直接跳过，尝试下一个元素。这是本题的情况。然而，如果 target 是小于 0 的，你是不能因为 nums[i] 大于 targe 直接 continue 的，这是因为如果 target 小于 0，比如 -11，但是 nums[i] 是 -6，-6 大于 -11，但是后续的元素虽然比 nums[i] 大，但是也可能是负数，比如 -5，因此，三数之和依然是有可能等于 target 的。
去重细节
去重 i 指针指向的元素的时候
i 指针指向的是 nums 里遍历的元素，这个元素重复了，应该直接跳过去。
但这里有一个问题，是判断 nums[i] 与 nums[i + 1] 是否相同，还是判断 nums[i] 与 nums[i-1] 是否相同。
有同学可能想，这不都一样吗。其实不一样！
都是和 nums[i] 进行比较，是比较它的前一个，还是比较它的后一个。
如果我们的写法是 这样：
if (nums[i] == nums[i + 1]) { // 去重操作
continue;
}
那我们就把三元组中出现重复元素的情况直接 pass 掉了。 例如 {-1, -1 ,2} 这组数据，当遍历到第一个 -1 的时候，判断 下一个也是 -1，那这组数据就 pass 了。
我们要做的是 不能有重复的三元组，但三元组内的元素是可以重复的！
那么应该这么写：
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
这么写就是当前使用 nums[i]，我们判断前一位是不是一样的元素，在看 {-1, -1 ,2} 这组数据，当遍历到 第一个 -1 的时候，只要前一位没有 -1，那么 {-1, -1 ,2} 这组数据一样可以收录到 结果集里。
这是一个非常细节的思考过程
left 与 right 的去重
如果 nums[i]+nums[left]+nums[right] 不为 target，判不判断 nums[right] 和 nums[right-1] 相等或者 nums[left] 和 nums[left+1] 相等其实没什么意义，即使相等，nums[i]+nums[left]+nums[right] 不为 target，还是要移动 left 或者 right，无非是再次出现 nums[i]+nums[left]+nums[right] 不为 target。所以 nums[i]+nums[left]+nums[right] 不为 target 的时候，不需要管 left 和 right 跟他们的下一个元素是否相等。我们只需要判断 nums[i]+nums[left]+nums[right] 等于 target 的时候，left 和 right 跟他们的下一个元素是否相等。
如果 nums[i]+nums[left]+nums[right] 等于 target 的时候， nums[right] 和 nums[right-1] 相等，那就要移动 right，nums[left] 和 nums[left+1] 相等，那就要移动 left，两头都要判断，避免添加重复的三元组合。
判断完之后，还要移动一次，查找下一个三元组合。
其实判断左右指针是否重复，还有一个更加简单的方法，就是，直接把上一次 nums[i]+nums[left]+nums[right] 等于 target 的时候的 nums[left] 和 nums[right] 记下来，下次再出现 nums[i]+nums[left]+nums[right] 等于 target 的情况的时候，对比一下即可，这比让 nums[left] 和 nums[left-1] 对比要更加简单和好理解。
简单总结
其实求两数之和的时候,我们也可以这样做，先对数组进行排序，然后用一个指针指向 nums 的开头,一个指向 nums 的末尾,相向而行,查找和为 target 的组合，但是 1. 两数之和 这道题要求返回元素下标，我们一开始对数组进行排序的时候就打乱了下标，所以只能用哈希表。
如果需要返回下标，那就无法用双指针法，因为双指针法需要排序，会改变下标，这个时候就需要考虑使用哈希法，如果需要返回元素而不是元素的下标，那就先排序，然后再尝试用哈希法。
如果题目要求组合中的所有元素都来自于一个数组，而且一个元素只能用一次，其实这个时候，你就只能用先排序然后双指针的方法了，除此之外没有别的办法可以保证这一点。至于结果去重，那都是额外的附加条件，决定了题目解法的，就是要求组合中的所有元素都来自于一个数组，而且一个元素只能用一次。
解题
public List<List<Integer>> threeSum(int[] nums) {
//用双指针法
List<List<Integer>> result = new ArrayList<>();
// 首先就是要排序
Arrays.sort(nums);
for(int i=0;i<nums.length;i++){
// 如果第一个元素就大于0了，那后面的元素就更大了（排过序了），直接返回
if(nums[i]>0){
break;
}
if(i>0 && nums[i]==nums[i-1]){
// 跳过重复元素
continue;
}
int left = i+1,right=nums.length-1;
while(right>left){
int sum = nums[i]+nums[left]+nums[right];
if(sum<0){
left++;
}else if(sum>0){
right--;
}else{
List<Integer> combination = Arrays.asList(nums[i],nums[left],nums[right]);
result.add(combination);
//跳过重复元素
while((right-1)>left && nums[right] == nums[right-1]){
right--;
}
while(right>(left+1) && nums[left] == nums[left+1]){
left++;
}
// 跳过重复元素之后，两个指针都要移动
right--;
left++;
}
}
}
return result;
}
简化版本，好记一些
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for(int i=0;i<nums.length;i++){
if(nums[i]>0){
break;
}
// 排除相邻元素的重复
if(i>0 && nums[i] == nums[i-1]){
continue;
}
int left = i+1;
int right = nums.length-1;
int targetSum = 0-nums[i];
while(left < right){
// 排除相邻元素的重复
if(left > i+1 && nums[left] == nums[left-1]){
left++;
continue;
}
if(right < nums.length-1 && nums[right] == nums[right+1]){
right--;
continue;
}
int nowSum = nums[left]+nums[right];
if(nowSum < targetSum){
left++;
}else if(nowSum > targetSum){
right--;
}else{
List<Integer> oneComb = new ArrayList<>();
oneComb.add(nums[i]);
oneComb.add(nums[left]);
oneComb.add(nums[right]);
result.add(oneComb);
left++;
right--;
}
}
}
return result;
}
}
另一种去重 left 和 right 的方法
public List<List<Integer>> threeSum(int[] nums) {
// 因为我们要返回元素本身，而不是索引，所以可以进行排序
// 排序之后，我们就可以使用双指针
// 然后移动一个元素，在后面的范围里面用双指针法，找组合，
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for(int i=0;i<nums.length;i++){
if(nums[i]>0){
break;
}
// 如果当前元素跟上一个元素相同，则直接跳过查找
if(i>0 && nums[i]==nums[i-1]){
continue;
}
int target = 0- nums[i];
int left = i+1,right = nums.length-1;
// 记住上一次的left和right，帮助去重
Integer lastLeftEle = null;
Integer lastRightEle = null;
// 因为我们要找两个元素，区间只有一个元素是不行的
while(left<right){
int nowSum = nums[left]+nums[right];
if( nowSum<target ){
left++;
}else if( nowSum>target ) {
right--;
}else{
if((lastLeftEle == null && lastRightEle ==null) || (lastLeftEle!=nums[left] && lastRightEle!=nums[right] ) ){
List<Integer> combination = new ArrayList<>();
combination.add(nums[i]);
combination.add(nums[left]);
combination.add(nums[right]);
result.add(combination);
lastLeftEle = nums[left];
lastRightEle = nums[right];
}
right--;
left++;
}
}
}
return result;
}