LeetCode #15 3Sum

Posted on | Post modified | In , , , , , ,

Problem

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.

Example

1
2
3
4
5
6
7
Given array nums = [-1, 0, 1, 2, -1, -4],

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

Solution1 (Base solution)

Method: Backtracking

Time Complexity:

Space Complexity:

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
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution:
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()

        def is_a_solution(answer, k, info):
            return k == 3
        
        def process_solution(answer, k, info):
            if sum(answer[1:]) == 0:
                if answer[1:] not in ret:
                    ret.append(answer[1:])
        
        def construct_candidates(answer, k, info):
            candidates = []
            if k == 1:
                candidates = info[:]
            else:
                max_num = answer[-1]
                for val in info:
                    if val >= max_num and \
                       info.count(val) > answer.count(val):
                        candidates.append(val)
            return candidates
        
        def backtracking(answer, k, info):
            if is_a_solution(answer, k, info):
                process_solution(answer, k, info)
            else:
                k += 1
                candidates = construct_candidates(answer, k, info)
                for candidate in candidates:
                    answer.append(candidate)
                    backtracking(answer, k, info)
                    answer.pop()
        
        ret = []
        backtracking([float('-inf')], 0, nums)
        
        return ret

or

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution:
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()

        def is_a_solution(answer, k, info):
            return k == 3
        
        def process_solution(answer, k, info):
            if sum(answer[1:]) == 0:
                if answer[1:] not in ret:
                    ret.append(answer[1:])
        
        def construct_candidates(answer, k, info):
            candidates = []
            if k == 1:
                candidates = info[:]
            else:
                max_num = answer[-1]
                for val in info:
                    if val >= max_num and \
                       info.count(val) > answer.count(val):
                        candidates.append(val)
            return candidates
        
        def backtracking(answer, k, info):
            if k == 3:
                if sum(answer) == 0 and answer not in ret:
                    ret.append(answer[:])
            else:
                k += 1
                candidates = []

                if k == 1:
                    candidates = info[:]
                else:
                    candidates += [val for val in info if val >= answer[-1] and info.count(val) > answer.count(val)]
                    
                for candidate in candidates:
                    answer.append(candidate)
                    backtracking(answer, k, info)
                    answer.pop()
        ret = []
        backtracking([], 0, nums)
        
        return ret

Solution2

Method:

Time Complexity: O(n^2)

Space Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) < 3:
            return []
        nums.sort()
        res = set()
        for i, v in enumerate(nums[:-2]):
            if i >= 1 and v == nums[i-1]:
                continue
            d = {}
            for x in nums[i+1:]:
                if x not in d:
                    d[-v-x] = 1
                else:
                    res.add((v, -v-x, x))
        return list(map(list, res))

or

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
class Solution:
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        nums.sort()
        for i in range(len(nums)-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            
            l, r = i+1, len(nums)-1
            
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s < 0:
                    l +=1 
                elif s > 0:
                    r -= 1
                else:
                    res.append((nums[i], nums[l], nums[r]))
                    while l < r and nums[l] == nums[l+1]:
                        l += 1
                    while l < r and nums[r] == nums[r-1]:
                        r -= 1
                    l += 1; r -= 1
        return res