18.leetcode题目讲解（Python）：四数之和

题目如下：

如果你是按题目顺序进行的练习，那么之前已经多次做个类似的题目了。这类型的题目主要需要注意的地方：

1. 将给定输入的数据进行排序后可以更方便的寻找答案
2. 避免无效计算（输入的数据长度过小，数据最大N个数总和小于目标或者数据最小N个数的总和大于目标）
3. 避免生成重复的答案(跳过 'num[i] == num[i - 1]' ），也可以利用Python的特性，将答案转换为 set 再转换为list来消除重复的答案
4. 注意索引的范围

我初次编写的时候采用比较容易想到的解法方案，可以打败50.3%的其他代码，如下：

class Solution:
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums = sorted(nums)
        res = []

        if not nums or len(nums) < 4:
            return res

        if nums[0] + nums[1] + nums[2] + nums[3] > target:
            return res

        if nums[-1] + nums[-2] + nums[-3] + nums[-4] < target:
            return res

        for i in range(0, len(nums)):
            if nums[i] + nums[-1] + nums[-2] + nums[-3] < target:
                continue
            for j in range(i + 1, len(nums) - 2):
                if nums[i] + nums[j] + nums[-2] + nums[-1] < target:
                    continue
                x = j + 1
                y = len(nums) - 1
                while x < y:
                    if nums[i] + nums[j] + nums[x] + nums[y] == target:
                        res.append([nums[i], nums[j], nums[x], nums[y]])
                        x = x + 1
                        while x < y and nums[x] == nums[x - 1]:
                            x = x + 1
                    elif nums[i] + nums[j] + nums[x] + nums[y] < target:
                        x = x + 1
                    else:
                        y = y - 1

        rr = []
        for r in res:
            if r not in rr:
                rr.append(r)
        return rr

完成了这道题目后，发现网站上 [[zhuyinghua1203]] 利用了递归的思路给出了这类题目通用的解决算法，挺棒，他给出的参考代码如下：

def fourSum(self, nums, target):
    nums.sort()
    results = []
    self.findNsum(nums, target, 4, [], results)
    return results

def findNsum(self, nums, target, N, result, results):
    if len(nums) < N or N < 2: return

    # solve 2-sum
    if N == 2:
        l,r = 0,len(nums)-1
        while l < r:
            if nums[l] + nums[r] == target:
                results.append(result + [nums[l], nums[r]])
                l += 1
                r -= 1
                while l < r and nums[l] == nums[l - 1]:
                    l += 1
                while r > l and nums[r] == nums[r + 1]:
                    r -= 1
            elif nums[l] + nums[r] < target:
                l += 1
            else:
                r -= 1
    else:
        for i in range(0, len(nums)-N+1):   # careful about range
            if target < nums[i]*N or target > nums[-1]*N:  # take advantages of sorted list
                break
            if i == 0 or i > 0 and nums[i-1] != nums[i]:  # recursively reduce N
                self.findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
    return

ps：如果您有好的建议，欢迎交流 :-D，也欢迎访问我的个人博客：tundrazone.com