【算法】三数之和

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]){}
}