题目大意：
三数之和
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=15
解题思路分析：
本题是2sum的升级版，但是解题思路却完全不一样。要想找到3个数的和为0，我们需要先确定一个数字，然后再找到另外两个数之和与第一个数字是相反数，这虽然是一句废话，但是却能得到一个结论，即满足条件的三个数字，要么全是0，要么必定有正有负，全是正数或者全是负数是无法满足和为0的。因此，我们首先可以给数组按照大小升序排列，排列后，从数组第一个数字开始循环，设当前数字为n1，接下来我们需要找后两个数字，这时需要第二层循环，本层循环需要使用到双指针，左指针指向n1右侧第一个数字n2，右指针指向数组最后的数字n3，这样三个数字已经集齐，我们查看n1+n2+n3的和sum，如果sum大于0，此时向左移动右指针，使得n3变小。同理，如果sum小于0，向右移动左指针使n2变大。如果sum等于0，当前的n1,n2,n3即是一个合理解。找到合理解后，同时向右移动左指针，向左移动右指针。
另外第一层循环时可以做一个剪枝处理，当前数字如果大于0时，说明另外2个数字也都大于0，之后不会再出现合理解，可直接返回。
最后，本题还需要考虑去除重复结果，在第一层循环以及第二层循环移动2个指针时，如果当前数字等于之前数字，可以跳过。
实现代码：
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums); // 排序数组
// 返回结果
List<List<Integer>> res = new ArrayList<>();
// 循环数组，确定第一个数字
for(int i=0;i<nums.length;i++){
// 当前数字
int n = nums[i];
// 如果等于前一个数字，跳过
if(i>0&&n==nums[i-1]) continue;
// 当n大于0时，不会再找到合理解，结束循环
if(n>0) break;
// 定义左右两个指针，找到能组成合理解的另外两个数
int left=i+1,right=nums.length-1;
// 当左指针小于右指针
while(left<right){
// 左指针数字
int l=nums[left];
// 右指针数字
int r=nums[right];
// 三个数字之和
int sum=n+l+r;
// 和等于0时为合理解
if(sum==0){
// 将三个数字加入返回结果
res.add(Arrays.asList(n,l,r));
// 向右移动左指针，找到一个不等于当前左指针数字的下一个数
while(left<right&&nums[left]==l) left++;
// 向左移动右指针，找到一个不等于当前右指针数字的下一个数
while(left<right&&nums[right]==r) right--;
}else if(sum<0){ // 和小于0
left++; // 向右移动左指针，增加左指针数字
}else{ // 和大于0
right--; // 向左移动右指针，减小右指针数字
}
}
}
return res;
} 本题解法执行时间为26ms。
Runtime: 26 ms, faster than 97.02% of Java online submissions for 3Sum.
Memory Usage: 55.9 MB, less than 5.29% of Java online submissions for 3Sum.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-15-3sum-解题思路分析/
View Comments (0)