三数之和

0x1 题目详情

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

测试用例： 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

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

0x2 解题思路

这道题是怎么想到三指针的呢？因为我第一遍做过了...，做这道题之前，我们想想双指针的使用方法是怎样的？

使用双指针一般都需要对数组进行排序，然后数组首尾分别放置一个指针，两个指针的指向内容如果符合规则，移动某个指针，如果不符合某个规则，然后移动另外一个，要么等到二者相遇，要么直接得出答案。

那么这道题就可以使用三指针(因为要求三个数据项)。我们以数组[-4,-1,-1,-1,1,2,2]为例：

三指针中我们固定指针i，在处理数组中的每个元素nums[i]时，我们使用left、right两个指针处理i之后的所有元素，不断移动left、right两个指针，直到它们相遇，表示与元素nums[i]的有关的三数之和都处理完了，可以开始处理下一个元素了。

去重的处理已经在图中标注了哦。

0x3 具体代码

因为使用排序，并且在遍历每个元素时的复杂度为$O(N^2)$,所以的总的时间复杂度为：$min(O(NlogN),N^2)=N^2$。具体实现完全按照图中的思路。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result=new ArrayList<>();
        if(nums== null || nums.length<3){
            return result;
        }
        //
        Arrays.sort(nums);
        int[] curResult=null;

        int left=0;
        int right=0;
        int target=0;
        //使用curPtr遍历每个nums中的每个元素

        for(int i=0;i<nums.length;i++){
            //对于每一个元素，如果和前一个元素相等，表示这个元素的三数之和已经求过了
            //直接跳过就行了
            if(i-1>-1 && nums[i-1]==nums[i]){
                continue;
            }
            left=i+1;
            right=nums.length-1;
            target=-nums[i];
            while(left<right){
                if(nums[left]+nums[right]<target){
                    left++;
                }else if(nums[left]+nums[right]>target){
                    right--;
                }else{
                    if(right+1<nums.length && nums[right]==nums[right+1]){
                        right--;
                        continue;
                    }
                    //如果当前right指向的元素和right+1相等，直接跳过，因为包含
                    //right+1的三数之和结果已经求过了，left-1同理
                    else if(left-1>i && nums[left-1]== nums[left]){
                        left++;
                        continue;
                    }
                    result.add(Arrays.asList(new Integer[]{nums[i],nums[left],nums[right]}));
                    right--;
                    left++;
                }
            }
        }
        return result;

    }
}

0x4 课后总结

会了三指针的使用方法，那么关于任何求数组中三个数的问题都可以通过对三指针的变形求解。比如求数组中最接近某个值的三个数，大于某个值且最接近的三个数等等。并且使用多指针的难点主要是考虑何时移动指针，这个问题搞清楚后，问题一般都会有解了。

最后记住使用双指针、三指针等的时候一般都需要数组有序哦!