1. & 15. K-sum 问题

Ksum问题：

第一种方法：暴力法，遍历 K 轮，求几个数字的和就遍历几轮。但是由于每遍历一轮都需要 的时间复杂度，因此总的时间复杂度会达到 。

第二种方法：双指针。这种方法需要先对输入的数组进行排序（时间复杂度 ），以最基本的 2sum 问题为例，用首尾两个指针，首指针从头开始向后遍历，尾指针从尾部开始向前遍历。如果它们指向的数字之和大于 target ，则尾指针向前移动；如果小于 target ，则首指针向后移动；直至最终和等于 target 。2sum 以上的问题都可以先固定 个数字，将其转化为 2sum 问题。
【补充】：这种方法可能存在一个问题：如果原始的输入数据是无序的，而且要求输出的是数字的索引而非数字本身，那么这种方法反而会很麻烦，因为排序会改变数字的索引，此时输出的索引是排序后的索引而非原始的索引。所以在这种情形下这种方法就不太合适了（比如leetcode的第一题：2sum），此时可以改用哈希表的方法。

第三种方法：使用哈希表。以2sum问题的哈希表解法为例：

• 只需要遍历一遍数组，在遍历的过程中把target和当前元素的差作为key，当前元素的下标作为value记录到哈希表中。然后每遍历到一个元素，就在哈希表中查找它是否已经被添加进来了。如果是，则返回它对应的value以及当前元素的索引。
• 这种做法是以空间换时间，时间复杂度为 ，空间复杂度也为 。

leetcode 2sum问题：

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if len(nums) < 2:
            return None
        temp = dict()
        for i in range(len(nums)):
            if nums[i] in temp:
                return [temp[nums[i]], i]
            else:
                temp[target-nums[i]] = i # 这样能保证输出索引是按递增顺序排序的
        return None

如果题目要求输出的是数字本身。那么排序+双指针的解法就可以用。排序的时间复杂度是 ，双指针遍历的时间复杂度是 ，因此总的时间复杂度是 ，空间复杂度是 。代码如下：

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if len(nums) < 2:
            return None
        res = []
        nums.sort()
        lo, hi = 0, len(nums)-1
        while lo < hi:
            s = nums[lo] + nums[hi]
            if s < target:
                lo += 1
            elif s > target:
                hi -= 1
            else:
                return [nums[lo], nums[hi]]

对于3sum和4sum问题，因为元素可能会重复出现，此时2sum的哈希表解法并不太适用，因为对重复元素的处理不太方便。此时最好的方法是排序+双指针的解法，3sum的时间复杂度为 ，4sum的时间复杂度为 。代码如下：

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) < 3:
            return None
        res = []
        nums.sort() # 双指针法必须要先排序
        for i in range(len(nums)-2):
            if i > 0 and nums[i] == nums[i-1]: # 组间去重
                continue
            lo, hi = i+1, len(nums)-1
            while lo < hi:
                s = nums[i] + nums[lo] + nums[hi]
                if s < 0:
                    lo +=1 
                elif s > 0:
                    hi -= 1
                else:
                    res.append((nums[i], nums[lo], nums[hi]))
                    while lo < hi and nums[lo] == nums[lo+1]: # 组内去重
                        lo += 1
                    while lo < hi and nums[hi] == nums[hi-1]: # 组内去重
                        hi -= 1
                    lo += 1 # lo要向后移一位
                    hi -= 1 # hi要向前移一位
        return res
    
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if len(nums) < 4:
            return None
        res = []
        nums.sort()
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]: # 组间去重
                continue
            for j in range(i+1, len(nums)):
                if j > i+1 and nums[j] == nums[j-1]: # 组间去重
                    continue
                lo, hi = j+1, len(nums)-1
                while lo < hi:
                    s = nums[i] + nums[j] + nums[lo] + nums[hi]
                    if s < target:
                        lo += 1
                    elif s > target:
                        hi -= 1
                    else:
                        res.append([nums[i], nums[j], nums[lo], nums[hi]])
                        while lo < hi and nums[lo] == nums[lo+1]: # 组内去重
                            lo += 1
                        while lo < hi and nums[hi] == nums[hi-1]: # 组内去重
                            hi -= 1
                        lo += 1
                        hi -= 1
        return res

这里要注意的是要进行两组去重：组间去重和组内去重。