15. 3Sum

使用Two Pointers，注意排序，处理重复，数组越界问题。

注意要对数组进行排序，因为要比较大小决定指针移动方向，没有排序会跳过某些数字。

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    // sort the list !!!
    Arrays.sort(nums); 
    for (int i = 0; i < nums.length - 2; i++) {
        // skip the same i value
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        // start binary search
        int target = -nums[i];
        int l = i + 1,
            r = nums.length - 1;
        while (l < r) {
            if (nums[l] + nums[r] == target) {
                res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                l++;
                r--;
                while (l < r && nums[l] == nums[l - 1]) l++; // skip the same l value
                while (l < r && nums[r] == nums[r + 1]) r--; // skip the same r value
            } else if (nums[l] + nums[r] < target) {
                l++;
            } else {
                r--;
            }
        }
    }
    return res;
}

紫色是i经过的区域，绿色是l, r移动的区域。

这三句是防止i, j, k重复的判断，i, l不能和它前面的数字相等，l不和它后面的数字相等。题目要求不能有重复的结果。

if (i > 0 && nums[i] == nums[i - 1]) continue;
while (l < r && nums[l] == nums[l - 1]) l++; 
while (l < r && nums[r] == nums[r + 1]) r--;

时间复杂度O(n^2)(for里面套while)，空间复杂度O(1)

1. 3Sum Closest，改改条件

public int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);
    int cloest = nums[0] + nums[1] + nums[2];
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        int l = i + 1,
            r = nums.length - 1;
        while (l < r) {
            int value = nums[i] + nums[l] + nums[r];
            if (Math.abs(value - target) < Math.abs(cloest - target)) {
                cloest = value;
            }
            if (value == target) {
                return value;
            } else if (value < target) {
                l++;
            } else {
                r--;
            }
        }
    }
    return cloest;
}