LeetCode 15. 3Sum

Description

Given an array nums of n integers, are there elements abc 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.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Explanation

Three sum is a follow-up question for two sum.

For three sum, we are going to find all possible triplets which each of the triplets meets following criteria:

num1 + num2  + num3 = 0

Just by making some modifications to equation, num1 + num2 = -num2. This is same as the two sum problem: num1 + num2 = target.

So for each number in the input array, we can use two sum approach to find whether there are two numbers in the rest of array add up together equal to the negative value of the number.

Java Solution

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        
        if (nums == null || nums.length < 3) {
            return results;
        }
        
        Arrays.sort(nums);
        
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            
            int target = -nums[i];
            int left = i + 1;
            int right = nums.length - 1;
            
            twoSumHelper(nums, results, target, left, right);
        }        
        
        return results;
    }
    
    private void twoSumHelper(int[] nums, List<List<Integer>> results, int target, int left, int right) {
        while (left < right) {
            if (nums[left] + nums[right] == target) {
                List<Integer> triplet = new ArrayList<>();                
                triplet.add(-target);
                triplet.add(nums[left]);
                triplet.add(nums[right]);
                results.add(triplet);
                
                left++;
                right--;
                
                while (left < right && nums[left] == nums[left - 1]) {
                    left++;
                }
                while (left < right && nums[right] == nums[right + 1]) {
                    right--;
                }
            } else if (nums[left] + nums[right] > target) {
                right--;
            } else if (nums[left] + nums[right] < target) {
                left++;                
            }
        }        
    }
}

Python Solution

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = []
        nums = list(sorted(nums))
        
        for i in range(0, len(nums)):
            if i != 0 and nums[i] == nums[i - 1]:
                continue
                
            num = nums[i]
            self.twosum_helper(nums[i + 1:], -num, result)
        
        return result
    
    def twosum_helper(self, nums, target, result):
        
        i = 0
        j = len(nums) - 1
        while i < j:
            if nums[i] + nums[j] == target:
                triplet = [nums[i], nums[j], -target]
                result.append(triplet)            
                i += 1
                j -= 1
                while i < j and nums[i] == nums[i - 1]:
                    i += 1
                while i < j and  nums[j] == nums[j + 1]:
                    j -= 1
                    
            elif nums[i] + nums[j] > target:
                j -= 1
                
            elif nums[i] + nums[j] < target:
                i += 1
  • Time complexity: O(N^2).
  • Space complexity: O(N).

6 Thoughts to “LeetCode 15. 3Sum”

  1. In the java solution, why do we -2 to the length when iterating here?:
    for (int i = 0; i < nums.length – 2; i++) {
    After I edited my code to have " i < nums.length -2" instead of " i < nums.length", it works!

    Thank you!

  2. This program returns duplicate triplets as well. Do you think we should have an additional method for checking the duplicates?

Leave a Reply

Your email address will not be published. Required fields are marked *