题目：
思路：排序 + 双指针
nSum 系列问题的核心思路就是排序 + 双指针 ；
指针往中间走！和快排一样；
为什么两数之和不能用双指针？
双指针需要数组排序，而两数之和需要返回的是索引，排序后索引就乱了 ！
双指针思想：根据sum的大小调整左右指针 ！ ；
但是，这样实现会造成重复的结果，比如说 nums = [1,1,1,2,2,3,3], target = 4，得到的结果中 [1,3] 肯定会重复；
所以当nums[left]与下一个数nums[left+1]相等则left++跳过，right同理！
注意：
- 三数之和时，left必须从i+1开始，否则双指针时会重复使用num[i] ！
- 双指针的while条件是lo < hi ，没有等于 ！等于则两个指针指向的数就重复了！
区别于二分法while中是 lo <= hi - 第一次去重时，和前一个数比较；
- 第二次去重时，先存入，然后用while去重，用当前数和下一个数比较，而不是和前一个数比较，相同则跳过; 而在for遍历 nums[i] 时，是和前面一个数比较；
Java实现：
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// 返回的是数而不是索引 ！
List<List<Integer>> r=new ArrayList<>();
if(nums.length==0){
return r;
}
// 1.先排序
Arrays.sort(nums);
for(int i=0;i<nums.length;i++){
// 去重1
if(i>0 && nums[i]==nums[i-1]){ // 必须先算nums[i] !
continue; // 遍历下一个 i
}
// 如果i>0，而数组又是递增的，则注定无法凑出0 ！
if(nums[i]>0){
continue;
}
// 2.双指针找为0-nums[i]的两个数，
int target=0-nums[i];
int left=i+1; // left必须从i+1开始，否则会重复使用num[i] ！
int right=nums.length-1;
while(left<right){
int sum=nums[left]+nums[right];
// 根据sum来调整指针
if(sum>target){
right--;
}else if(sum<target){
left++;
}else if(sum==target){
r.add(Arrays.asList(nums[i],nums[left],nums[right]));
// 去重2：第一次添加到List后就要去重！
while(left<right && nums[left]==nums[left+1]){
left++;
}
while(left<right && nums[right]==nums[right-1]){
right--;
}
// 继续寻找
right--;
left++;
}
}
}
return r;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89229.html
