Leetcode 15. 3Sum

Posted on | | 阅读数
Words count in article: 191 | Reading time ≈ 1

Question

Solution1

将数据分为0，正数，负数。然后考虑000，-0+，-++，—+几种情况。

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
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans = []
        nums = sorted(nums)
        nums_p = [elem for elem in nums if elem > 0]
        nums_n = [elem for elem in nums if elem < 0]
        nums_zero = [elem for elem in nums if elem == 0]
        
        positive = set(nums_p)
        negative = set(nums_n)
        
        #3 Zero
        if len(nums_zero) > 2:
            ans.append([0, 0, 0])
        
        # 1 Zero 1 postive 1 negative
        if len(nums_zero) > 0:
            for elem in nums_p:
                if -elem in negative:
                    ans.append([-elem, 0, elem])
        
        # 2 positive 1 negative
        for i in range(len(nums_p)-1):
            for j in range(i+1, len(nums_p)):
                diff = -nums_p[i] - nums_p[j]
                if diff in negative:
                    ans.append([diff, nums_p[i], nums_p[j]])
        
        # 2 negative 1 positive
        for i in range(len(nums_n)-1):
            for j in range(i+1, len(nums_n)):
                diff = -nums_n[i] - nums_n[j]
                if diff in positive:
                    ans.append([nums_n[i], nums_n[j], diff])
        return [list(t) for t in set(tuple(_) for _ in ans)]