15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

首先采用暴力解法,主要在于如何去重，为了不利用set等额外数据空间进行排序处理:

        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> ret=new ArrayList<>();
            //因为答案要求唯一，所以先进行排序，一个有序的数组下，可以保证下一位必定大于或者等于上一位。
            //这样，我们可以在遍历时判断当前位是否等于上一位，如果等于那么说明取值不唯一，所以直接跳过
            Arrays.sort(nums);
            //暴力解法:O^3复杂度。
            for(int i=0;i< nums.length-2;i++){
                if (i==0 || nums[i]!=nums[i-1]){
                    for(int j=i+1;j< nums.length-1;j++){
                        if (j==i+1 || nums[j]!= nums[j-1]){
                            for (int k=j+1;k< nums.length;k++){
                                if (k==j+1 || nums[k]!=nums[k-1]){
                                    if (nums[i]+ nums[j]+nums[k]==0){
                                        List<Integer> item=new ArrayList<>();
                                        Collections.addAll(item,nums[i],nums[j],nums[k]);
                                        ret.add(item);
                                    }
                                }
                            }
                        }
                    }
                }
            }
            return ret;
        }

接着进行相应优化:

        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> ret=new ArrayList<>();
            //因为答案要求唯一，所以先进行排序，一个有序的数组下，可以保证下一位必定大于或者等于上一位。
            //这样，我们可以在遍历时判断当前位是否等于上一位，如果等于那么说明取值不唯一，所以直接跳过
            Arrays.sort(nums);
            for(int i=0;i< nums.length-2;i++){
                if (i==0 || nums[i]!=nums[i-1]){
                    //相较于暴力解法，实质我们在i轮遍历确定下nums[i]的具体数值后，剩下的两位数只需要满足 和=-nums[i]即可
                    //nums[j]一旦变大，那么nums[k]必定是需要减小才能满足两者和依旧固定,并且因为有序，
                    //所以我们可以通过这一特性来缩小j和k的取值范围，我们通过两个指针即可使得原本剩余的O(n^2)复杂度变成O^(n)
                    //具体作为为采用双指针，j为指向剩余数据头部指针，k为指向剩余数据尾部指针
                    int k=nums.length-1;
                    //这样优化后，每次确定i之后，剩余部分数据中j和k总共移动最多为nums.lenghth-i次约为n，而之前双重循环为n^2
                    int j=i+1;
                    while (j<k){
                        if (j==i+1 || nums[j]!= nums[j-1]){
                            int temp=nums[j]+nums[k];
                            if (temp>-nums[i]){
                                //需要移动k，使得取值变小
                                k--;
                                continue;
                            }
                            if (temp==-nums[i]){
                                //找到符合
                                ret.add(new ArrayList<>(Arrays.asList(nums[i],nums[j],nums[k])));
                            }
                        }
                        j++;
                    }
                }
            }
            return ret;
        }