nSum 问题

Posted on In Disqus: Word count in article: 812 Reading time ≈ 1 mins.

nSum 问题

2 Sum

方法1：去重、排序、字典、穷举

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        cache = {}
        
        for i in range(len(nums)):
            residual = target - nums[i]
            
            if residual in cache:
                return [cache[residual], i]
            
            cache[nums[i]] = i
            
        return []

3 Sum

方法1：去重、排序、字典、穷举

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
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) <= 3 and sum(nums)!=0:
            return []
        
        res = []
        counter = collections.defaultdict(int)
        for i in nums:
            counter[i] += 1
            
        nums = sorted(counter.keys())
        
        for i in range(len(nums)):
            a = nums[i]
            
            if 3*a == 0 and counter[a] >= 3:
                res.append([a,a,a])
            
            for j in range(i+1, len(nums)):
                b = nums[j]
                
                if 2*b + a == 0 and counter[b] >= 2:
                    res.append([a, b, b])
                
                if 2*a + b == 0 and counter[a] >= 2:
                    res.append([a, a, b])
                    
                c = -a-b
                
                if c > b and counter[c] >= 1:
                    res.append([a, b, c])
        
        return res
tags: Leetcode nSum