leetcode15.三数之和

题目链接

排序+双指针夹逼法

对于本题，无论是暴力求解，还是使用哈希表求解，我觉得都不如排序之后使用左右夹逼的方法好理解。
解析：
针对数组
[-1, 0, 1, 2, -1, -4]

step1: sort arr

第一步需要将数组排序成有序的数组，对示例而言，排序之后的数组为
[-4, -1, -1, 0, 1, 2]

step2: left and right pointer clamp

排好序之后，我们需要做的就是对index [0 ~ arr.length - 2]位置的数进行遍历，以遍历到的每个数为基准，对遍历到的数的右边的数和数组中最后一个数进行夹逼，求出arr[i] + arr[p] + arr[q] == 0的所有数。附上我觉得非常好的题解说明的链接。
本题的难点在于各种case的考察与如何去重。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();
        for(int i = 0; i < nums.length - 2; i++){
            if(nums[i] > 0){
                break;
            }
            if(i > 0 && nums[i] == nums[i - 1]) {
                continue;
            } 
            for(int p = i + 1,q = nums.length - 1; p < q ;){
                if(nums[p] + nums[q] + nums[i] < 0){
                    while(p < q && nums[p] == nums[++p]);
                }else if(nums[p] + nums[q] + nums[i] > 0){
                    while(p < q && nums[q] == nums[--q]);
                }else{
                    list.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[p],nums[q])));
                    while(p < q && nums[p] == nums[++p]);
                    while(p < q && nums[q] == nums[--q]);
                }
            }
        }
        return list;
    }
}

对于程序，有几点需要说明：
第一处：

if(nums[i] > 0){
    break;
}

因为数组已经排好序了，如果基准数已经大于零，那么nums[p]和nums[q]都是比nums[i]要大的数字，所以可以直接跳出循环了。
第二处：

if(i > 0 && nums[i] == nums[i - 1]) {
    continue;
} 

如果有i > 0 && nums[i] == nums[i - 1]那么说明，基准数与前一个基准数相等，这样的话可以直接continue,因为即便出现了符合情况的arrayList，也是重复的。
第三处：
应该使用这种简明的写法

list.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[p],nums[q])));

来代替：

List<Integer> aList = new ArrayList<>();
aList.add(nums[i]);
aList.add(nums[p]);
aList.add(nums[q]);
list.add(aList)

排序的时间复杂度为O(n logn)，所以本题这种解法的时间复杂度为O(n ^ 2)；额外空间复杂度为O(1)。