Skip to content

15. 3Sum

🔗 Source

Intuition

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Naive Solution: Traverse the given array \(O(n^3)\) times.

Approach

  • Step 1: Sort the array so that we can use sliding window approach. (Sorting the array takes \(O(N\log N)\) times)
  • Step 2: Creat a hash map list and add all elements.
  • Step 3: For each element in the hash map, apply Two Sum approach!
    • Outer Loop: Selects the first element nums[i] and ensures it is not greater than 0.
    • Inner Loop: Selects the second element nums[j] and calculates the required third element as target = 0 - nums[i] - nums[j].
    • Hash Map Lookup: Uses the hash map to check if the third element exists and its index is greater than j to ensure the triplet is unique.
    • Update Loop Variables: Uses the hash map to update j and i to skip over duplicate elements.

Complexity

  • Time complexity: \(T(N) = O(N^2 + N\log N) = O(N^2)\)
  • Space complexity: \(O(N)\) as we implement a hash map. To optimize, we can use two pointer approach.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        if (nums.length < 3 || nums[0] > 0) {
            return res;
        }

        HashMap<Integer, Integer> list = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            list.put(nums[i], i);
        }

        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) {
                break;
            }
            for (int j = i + 1; j < nums.length - 1; j++) {
                int target = 0 - nums[i] - nums[j];
                if (list.containsKey(target) && list.get(target) > j) {
                    res.add(Arrays.asList(nums[i], nums[j], target));
                }
                j = list.get(nums[j]);
            }
            i = list.get(nums[i]);
        }
        return res;
    }
}