15. 3Sum

LeetCode

3Sum问题我们可以把它理解为2Sum的变种。2Sum问题是这样的：

给定一个target和一个数组nums，找出令等式nums[i] + nums[j] = target 成立的nums[i]和nums[j]。（和LeetCode原题有所区别）

对于这个我们自拟的2Sum问题，我们可以先对数组做快速排序，有序性使得坐标的单调移动与数值的单调变化保持一致。利用它我们可以使用双指针简介优雅地解决问题。

class Solution {
    public int[] myTwoSum(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        Arrays.sort(nums);
        int left = 0, right = nums.length - 1;
        for (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                return new int[] { nums[left], nums[right] };
            } else if (sum < target) {
                left++;
            } else {
                right++;
            }
        }
        return null;
    }
}

3Sum问题的题目则是这样的：

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

在这题中，其实我们可以把a + b + c = 0看作target + b + c = 0，也就是b + c = -target 。如此一来，在数学形式上就变成和2Sum一样了，所以同样可以先令数组有序，然后再利用有序性使用双指针解决。而区别主要在于target从固定的值变成了单调变化的值。

这两题的区别还在于，2Sum问题找到符合条件的tuple就立即返回，而3Sum问题则要找到所有符合条件的tuple（并且要无重复）。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        if (nums == null || nums.length < 3) {
            return new ArrayList<>();
        }
        
        Arrays.sort(nums);
        List<List<Integer>> lists = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            // no 3sum tuple in the rest of the sorted array
            if (nums[i] > 0) {
                return lists;
            }
            // If nums[i] is duplicated with nums[i - i], skip the current round
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] == 0) {
                    ArrayList<Integer> list = new ArrayList<>(3);
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    lists.add(list);
                    // skips duplicated elements (if it exists)
                    while (left < right && nums[left] == nums[left + 1]) {
                        left = left + 1;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right = right - 1;
                    }
                    // moves to the next element
                    left = left + 1;
                    right = right - 1;
                } else if (nums[i] + nums[left] + nums[right] > 0) {
                    right = right - 1;
                } else {
                    left = left + 1;
                }
            }
        }
        return lists;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {-1, 0, 1, 2, -1, -4};
        for (List<Integer> list : solution.threeSum(nums)) {
            System.out.println(list);
        }
    }
}