【算法】三数之和
1、题目
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1,2]
]
2、暴力算法
所有人的第一反应应该就是
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new LinkedList<List<Integer>>();
for (int i = 0; i < nums.length-2; i++) {
for (int j = i+1; j < nums.length-1; j++) {
for (int j2 = j+1; j2 < nums.length; j2++) {
if(nums[i]+nums[j]+nums[j2]==0) {
List<Integer> temp = new LinkedList<Integer>();
temp.add(nums[i]);
temp.add(nums[j]);
temp.add(nums[j2]);
result.add(temp);
}
}
}
}
return result;
}
但是如上的算法和结果有一定误差，如果题目中的例子，返回的结果是[[-1, 0, 1], [-1, 2, -1], [0, 1, -1]]第一个和第三个是重复的。我们需要想办法剔除
换一种思路，先排序，遍历数组，然后在剩下的数里边找合适的
public List<List<Integer>> threeSum2(int[] nums) {
Arrays.sort(nums);//先排序
List<List<Integer>> result = new LinkedList<List<Integer>>();
for(int i=0;i<nums.length-2;i++){//从小到大的遍历
int min =i+1, max = nums.length-1,current= nums[i];
//开始寻找和nums[i]加起来等于0的两个数，基本上可以判断，最大的数必须是大于等于0的，current是三个数里最小的，理应小于等于0，如果大于0的时候，基本上可以认为循环结束了。
if(max<0){return result;}
else if(current>0){break;}
while(min<max){
//先判断和是不是等于0
if(current+nums[min]+nums[max]==0){
List<Integer> temp = new LinkedList<Integer>();
temp.add(current);
temp.add(nums[min]);
temp.add(nums[max]);
result.add(temp);
while(min<max&&max==++max){}
while(min<max&&min==--min){}
}else if(current+nums[min]+nums[max]>0){
while(min<max&&max==++max){}//这句话是max向左移动，当左边的和原来的值一致的时候继续滑动，这样就避免了一样的值出现这种问题
}else if(current+nums[min]+nums[max]<0){
while(min<max&&min==--min){}
}
}
return result;
}
}
上述是我手打的基本的框架，然后调试过程中不断的添加补充值
//1. 先判断数组够不够三位，以及最大的大于等于0 最小的小于等于0
public List<List<Integer>> threeSum2(int[] nums) {
List<List<Integer>> result = new LinkedList<List<Integer>>();
if(nums.length<3||nums[0]>0||nums[nums.length-1]<0) return null;
Arrays.sort(nums);//先排序
.....
//2. 每次便利的时候i不应该加1，而是应该加到和前一个值不等
for (int i = 0; i < nums.length-2; ) {
。。。
while(i<nums.length-1&&nums[i]==++nums[i]){}
}
