Leetcode 15: 3Sum

In this exercise, we are looking for all the triplets adding up to 0 in an array of integers. We use solution building on the solution for 2-sum II: Input array is sorted.

a. Algorithm

As we have seen in Two Sum II, if the array is sorted and we have a target, we can solve 2-sum in O(n). The idea in 3-sum is to sort the array, and use the first number as target:

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    int n = nums.length;
    for (int i = 0; i < n-2;i++) {
        int target = -nums[i];
        // ... solve 2-sum on nums[i+1..n-1] and target;

Basic algorithm

The other benefit of sorting is to avoid duplicates. Everytime we encounter a new number that is the same as the previous one , we can just skip the iteration (see all the continue cases)

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    int n = nums.length;
    for (int i = 0; i < n-2;i++) {
        if (i>0 && nums[i] == nums[i-1]) {
            continue;
        }
        int target = -nums[i];
        int x = i+1;
        int y = n-1;
        while (x < y) {
            if (y<n-1 && nums[y] == nums[y+1]) {
                y--;
                continue;
            }
            if (x>i+1 && nums[x] ==…