三数之和
题目描述
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
思路
三数之和，暴力循环 O(N^3)肯定TLE所以不考虑
那么可以把时间复杂度暂定于O(N^2)
所以我们可以先排个序，然后再考虑；
因为遍历数组不可能避免，所以最外一层循环就是遍历。接着我们要考虑剩下一重循环怎么写。
因为最小数已经确定，我们只要使剩下两数之和为最小数的相反数即可，所以可以定义两个指针分别表述最小数后一个数，与最大数，然后两指针向中间靠拢，用一重循环，确定两数。
靠拢的条件就是三数之和小于0，那么小的要变大，t如果三数之和大于0，那么大的要变小。
大致逻辑框架就是这样。接下来要保证不会重复。
1.两指针判断一个数是否相等，若是则直接移动。
2.同一个数作为最小数一次即可，两次必然会重复
之后要考虑是否有特殊情况，例如传进来的数组长度是否小于3，或者是否传递空值等。
这两种情况不能返回null（被坑了一次。。。）。
最 后就是考虑能否优化，比如说最小数大于0，那么一定不存在解了，可以直接返回。
Java实现
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if(nums==null||nums.length<3){
return res;
}
Arrays.sort(nums);
for(int i=0;i<nums.length-2;i++){
if(nums[i]>0) break;
if(i>0&&nums[i]==nums[i-1]) continue;
int j=i+1;
int k=nums.length-1;
while(j<k){
if(nums[i]+nums[j]+nums[k]==0){
res.add(Arrays.asList(nums[i], nums[j], nums[k]));
while(j<k){
if(nums[j]==nums[j+1]) j++;
else if(nums[k]==nums[k-1]) k--;
else break;
}
j++;
k--;
}
else if(nums[i]+nums[j]+nums[k]<0){
j++;
}
else k--;
}
}
return res;
}
}
执行用时 : 54 ms, 在3Sum的Java提交中击败了95.66% 的用户
内存消耗 : 53.1 MB, 在3Sum的Java提交中击败了80.37% 的用户
