Three sum#

Levels: level-2

Data structures: array, hash-table

Practice Link#

LeetCode

Description#

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.

Python Solution#

 1class Solution(object):
 2    def threeSum(self, nums):
 3        """
 4        :type nums: List[int]
 5        :rtype: List[List[int]]
 6        """
 7        if not nums:
 8            return []
 9        res = []
10        nums.sort()
11        for i in range(len(nums) - 2):
12            # adjacent duplicate elements would cause duplicate triplets
13            if i > 0 and nums[i] == nums[i - 1]:
14                continue
15            l, r = i + 1, len(nums) - 1
16            while l < r:
17                s = nums[i] + nums[l] + nums[r]
18                if s < 0:
19                    l += 1
20                elif s > 0:
21                    r -= 1
22                else:
23                    res.append((nums[i], nums[l], nums[r]))
24                    # adjacent duplicate elements would cause duplicate triplets
25                    # Increment left and right until duplicates are eliminated
26                    while l < r and nums[l] == nums[l + 1]:
27                        l += 1
28                    while l < r and nums[r] == nums[r - 1]:
29                        r -= 1
30                    l += 1
31                    r -= 1
32        return res
33
34
35in_arrs = [
36    [-1, 0, 1, 2, -1, -4],
37    [1],
38    [],
39    None,
40]
41
42exp_out = [
43    set([
44        (-1, 0, 1),
45        (-1, -1, 2),
46    ]),
47    set([]),
48    set([]),
49    set([]),
50]
51
52if __name__ == "__main__":
53
54    sol = Solution()
55    for idx, nin in enumerate(in_arrs):
56        resout = sol.threeSum(nin)
57        resout = set(map(tuple, resout))
58        di = resout.symmetric_difference(exp_out[idx])
59        print(resout, di, False if di else True)