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++)…