博客

前言：这个系列分为1、15、18三个题，分别是两数之和、三数之和和四数之和。其中两数之和要返回两数的下标，其余是返回组成的数字。


1.两数之和


点评：用了个hash表来保存每个数的下标。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        a = {nums[i]:i for i in range(len(nums))}
        for i in range(len(nums)):
            other = target - nums[i]
            if other in a and a[other] != i:
                return [i, a[other]]
        return []

15.三数之和


点评：三数之和是在两数之和的基础上完成的。也就是将三个数分成一个数和另外两个数之和，循环一遍所有数且调用一遍twoSum。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        def towSum(nums, start, t):
            l, r = start , len(nums)-1
            res = []
            while l < r:
                a, b = nums[l], nums[r]
                s = a + b
                if s == t:
                    res.append([nums[l], nums[r]])
                    while l<r and nums[l]==a:l+=1
                    while l<r and nums[r]==b:r-=1
                elif s < t:
                    while l<r and nums[l]==a:l+=1
                elif s > t:
                    while l<r and nums[r]==b:r-=1
            return res
        nums = sorted(nums)
        res = []
        i = 0
        while i <len(nums)-1:
            other = 0 - nums[i]
            t = towSum(nums, i+1, other)
            for j in t:
                j.append(nums[i])
                res.append(j)
            while i<len(nums)-1 and nums[i]==nums[i+1]:i+=1
            i += 1
        return res

18.四数之和


点评：这里抽象成了nSum。将n重循环变成了递归调用，我们写好了twoSum的代码，如果n大于2的时候，就不停的递归调用n-1Sum，每次返回的结果可能有多个，所以需要遍历一遍。只要保证下标是递增的，而且顺序跳过相同的数字，就能保证最后得到的答案是唯一的。

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        def nSum(nums, n, start, target):
            N = len(nums)
            res = []
            if n < 2 or N < n:return res
            if n == 2:
                l, r = start, N-1
                while l < r:
                    a, b = nums[l], nums[r]
                    summ = a + b
                    if summ < target:
                        while l < r and nums[l]==a:l+=1
                    elif summ > target:
                        while l < r and nums[r]==b:r-=1
                    else:
                        res.append([a, b])
                        while l < r and nums[l]==a:l+=1
                        while l < r and nums[r]==b:r-=1
            else:
                i = start
                while i < N:
                    sub = nSum(nums, n-1, i+1, target-nums[i])
                    for cur in sub:
                        cur.append(nums[i])
                        res.append(cur)
                    while i < N-1 and nums[i]==nums[i+1]:i+=1
                    i += 1
            return res
        return nSum(sorted(nums), 4, 0, target)

总结：nSum问题，通过一个nSum函数秒杀，本质还是一个n重循环，这里用递归实现，但是里面的一些细节问题，比如如何使其子问题的结果不重复，这就需要多多写代码，多多理解了。