menu

[LeetCode] 015. 3Sum

Problem (Medium)

015. 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.

Example:

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

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

Approach 1: Brute Force (Time Limit Exceeded!)

Idea

3 loop to find all solutions.

Solution

class Solution1:
    def threeSum(self, nums):
        """ 
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ret = set()
        for i in range(len(nums)-2):
            for j in range(i+1, len(nums)-1):
                for k in range(j+1, len(nums)):
                    if nums[i] + nums[j] + nums[k] == 0:
                        ret.add(tuple(sorted([nums[i], nums[j], nums[k]])))
        return ret

Complexity

  • Time: $O(n^3)$
  • Space: $O(1)$

Approach 2: Sort the Numbers, then $O(n^2)$

Idea

» Check this link » And this link

Solution

    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ret = set()
        nums.sort()
        for i in range(len(nums)-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            j = i + 1
            k = len(nums) - 1
            # check sum of numbers at j and k equals to -num[i] or not
            while j < k:
                if nums[i] + nums[j] + nums[k] < 0:
                    j += 1
                elif nums[i] + nums[j] + nums[k] > 0:
                    k -= 1
                else:
                    ret.add(tuple(sorted([nums[i], nums[j], nums[k]])))
                    while j < k and nums[j] == nums[j+1]:
                        j += 1
                    j += 1
                    while j < k and nums[k-1] == nums[k]:
                        k -= 1
                    k -= 1
        return ret

Complexity

  • Time: $O(n^2)$
  • Space: $O(1)$



KF

Comments