几数之和分析，解法，优化和总结

2020 年 4 月 28 日
笔记
算法

1. 两数之和

总体的思路还是比较简单的，也就是用一个字典记录下我需要的值，如果在接下来的值中有匹配的值，就完成了目标，我在这里就不考虑这些了，在这里还是要考虑一些特殊的case和特殊的要求。

首先来看一下最简单的版本，写出这个版本就意味着面试gg。

def twoSum1(list1,target):
    res = []
    dic1 = {}
    for i in list1:
        if i not in dic1:
            dic1[target-i]=i
        else:
            res.append([i,dic1[i]])
    return res

print(twoSum([1,1,2,2,2,3,4,5],3))

[[2, 1], [2, 1],[2,1]]

从这个代码中我们很轻松的就可以看出很多漏洞。如果数字中有重复的值应该怎么办呢？就像下面显示的，如果list1里面有两个1 1 2 2 2 就是很明显的漏洞，如果我规定每个数字只能用一遍应该怎么办呢。对这个的改进就是在字典中保存我们的次数，在else里面append的时候线判断一下次数，就可以知道使用几次了。

def twoSum(list1,target):
    res = []
    dic1 = {}
    for i in list1:
        if i not in dic1:

            if target - i in dic1:
                dic1[target-i] = (i,dic1[target-i][1]+1) # 每有一个i，那么target-i在字典中的值就会多1
            else:
                dic1[target-i]=(i,1)   
        else:
            if dic1[i][1] >=1:
                res.append([i,dic1[i][0]])
                dic1[i] = (dic1[i][0],dic1[i][1]-1)
    return res

print(twoSum([1,1,2,2,2,3,4,5],3))
[[2, 1], [2, 1]]

从这里可以看出，我们已经有效的解决了次数只能用一遍的情况，还有一种情况，就是要求全不能重复。也就是对于这种情况，只能有一个[2,1]。首先我们可以只需要在上面的字典中做一点手脚就可以做到，也就是在字典的次数的统计，如果我把次数最大值也就设置成1，如果使用过就变成0，之后只要遇到相同的，都直接略过，就完成了目标。（这里有点像信号量和独占锁的关系有木有）

def twoSum(list1,target):
    res = []
    dic1 = {}
    for i in list1:
        if i not in dic1:
            if target - i in dic1:
                if dic1[target-i] == 0:
                    continue
            dic1[target-i]=(i,1)
        else:
            if dic1[i][1] ==1:
                res.append([i,dic1[i][0]])
                dic1[i] = (dic1[i][0],dic1[i][1]-1)
    return res

2. 三数之和

三数之和和两数之和有点像的，就是需要把数组多遍历一遍。里面主要的难点就是在于重复值的去除。如果按照上面利用字典的方式，对于重复值的去除是不太容易的事情。例如 3 2 1 3 这种排列，就可能导致重复的值。因此大致的思路就是先将数组排序，然后可以依赖排序的性质去寻找目标的三个值。我们先定义i,left,right三个数，其中i为数组的没一个元素.left,right分别为i右边的最左元素和最右元素。让left和right向中间靠拢，直到相遇。

那么在这里便可以进行去重，如果list1[left] == list1[left+1] 那么就要直接跳过。但在这里编程有一个细节，就是对于[0,0,0]这种情况，如果先判断跳过，那么我们的值就位空了，所以应该先将目标值加入res中，然后将left和right进行更新。

def threeSum(list1):
    list1 = sorted(list1)
    N1 = len(list1)
    res = []
    for i in range(N1):
        if list1[i] > 0:  return  res
        if i > 0 and list1[i] == list1[i-1]:continue
        left = i+1
        right = N1-1
        while left < right:
            if list1[i] + list1[right]+list1[left] == 0:
                res.append([list1[i] ,list1[right],list1[left]])
                while left < right and list1[left] == list1[left+1]:
                    left+=1
                while left < right and list1[right] == list1[right-1]:
                    right -= 1
                left += 1
                right -= 1
　　　　　　　　　　continue
            if list1[i] + list1[right]+list1[left] > 0:
                while left < right and list1[right] == list1[right-1]:
                    right -= 1
                right -=1
　　　　　　　　　　continue
            if list1[i] + list1[right]+list1[left] < 0:
                while left < right and list1[left] == list1[left+1]:
                    left+=1
                left += 1
    return res

这里有没有可以优化的点呢？显示有的。既然有了这个两数之和的那种思路，使用字典可以形成一个空间换时间的概念。这里直接用leetcode里面大神的解法，异常优秀

def threeSum(nums]):
        
        answers = set()
        
        negative_nums = [n for n in nums if n < 0]
        positive_nums = [n for n in nums if n > 0]
        zeros = [n for n in nums if n==0]
        negative_num_set = set(negative_nums)
        positive_num_set = set(positive_nums)
        
        if len(zeros)>0:
            if len(zeros)>=3:
                answers.add((0,0,0))
            for pos in positive_num_set:
                if -pos in negative_num_set:
                    answers.add((-pos,0,pos))
        
        
        
        for i in range(len(negative_nums)):
            for j in range(i):
                c = -(negative_nums[i] + negative_nums[j])
                if c in positive_num_set:
                    answers.add((min(negative_nums[i],negative_nums[j]),max(negative_nums[i],negative_nums[j]),c))
        
        for i in range(len(positive_nums)):
            for j in range(i):
                c = -(positive_nums[i] + positive_nums[j])
                if c in negative_num_set:
                    answers.add((c,min(positive_nums[i],positive_nums[j]),max(positive_nums[i],positive_nums[j])))
                    
        return [list(t) for t in answers]

3. 四数之和

事实上，四数之和和三数之和非常类似，也就是多了一个循环。

class Solution:
    def fourSum(self, nums, target) :
        res = []
        nums  = sorted(nums)
        N1 = len(nums)
        for i in range(N1):
            # if nums[i] > target:return res
            if i > 0 and nums[i] == nums[i-1]:continue
            tempTarget = target - nums[i]
            for j in range(i+1,N1):
                # if nums[j] > tempTarget:break
                if j > i+1 and nums[j] == nums[j-1]:continue
                left = j+1
                right = N1-1
                while left < right:
                    if nums[j]+nums[left]+nums[right] == tempTarget:
                        res.append([nums[i],nums[j],nums[left],nums[right]])
                        while left < right and nums[left] == nums[left+1]:
                            left += 1
                        while left < right and nums[right] == nums[right-1]:
                            right -=1
                        left += 1
                        right -=1
                        continue
                    if nums[j]+nums[left]+nums[right] > tempTarget:
                        while left < right and nums[right] == nums[right-1]:
                            right -=1
                        right -= 1
                        continue
                    if nums[j]+nums[left]+nums[right] < tempTarget:
                        while left < right and nums[left] == nums[left+1]:
                            left += 1
                        left += 1
        return res
print(Solution().fourSum([1,-2,-5,-4,-3,3,3,5],-11))

当然对于面试的时候要是能写出来这个其实就已经挺不错的了，但是这样非常暴力，有没有什么可以优化的地方呢？事实上是有的，主要就是再什么时候可以跳出循环，因为有了排序的步骤，因此可以对排序进行尽可能的优化。

1.在第for循环中，如果num[i] + 3*nums[i+1] >target:那么就可以直接break，因为这样可以认为后面不管取什幺元素都会大于target。这里我们为什么不能像3数之和直接判断nums[i]呢？因为3数之和的要求是target = 0 ，所以可以直接判断nums[i] > 0 就可以了。

2.相同的思路，对于nums[i] + 3*nums[-1] < target的情况，就可以认为这个是不存在的，直接continue掉就可以了。

2.对于每个循环，并不需要for 到他的最后一个元素，只要是倒数第4个元素就ok了。

3.对于初始化元素的判断。如长度小于4.

所以最终代码是

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        res = []
        nums  = sorted(nums)
        N1 = len(nums)
        if(nums is None or N1 < 4 ):
            return []
        for i in range(N1-3):
            if nums[i] + 3*nums[i+1] > target:return res
            if nums[i] + 3*nums[-1] < target: continue
            if i > 0 and nums[i] == nums[i-1]:continue
            tempTarget = target - nums[i]
            for j in range(i+1,N1-2):
                if nums[j]+2*nums[j+1] > target - nums[i]:break
                if nums[j] + 2*nums[-1] < target - nums[i]:continue
                if j > i+1 and nums[j] == nums[j-1]:continue
                left = j+1
                right = N1-1
                while left < right:
                    if nums[j]+nums[left]+nums[right] == tempTarget:
                        res.append([nums[i],nums[j],nums[left],nums[right]])
                        while left < right and nums[left] == nums[left+1]:
                            left += 1
                        while left < right and nums[right] == nums[right-1]:
                            right -=1
                        left += 1
                        right -=1
                        continue
                    if nums[j]+nums[left]+nums[right] > tempTarget:
                        while left < right and nums[right] == nums[right-1]:
                            right -=1
                        right -= 1
                        continue
                    if nums[j]+nums[left]+nums[right] < tempTarget:
                        while left < right and nums[left] == nums[left+1]:
                            left += 1
                        left += 1
        return res

最后也只到达了124ms，不知道什么地方还可以再优化，看了前排代码，也就差不多是这些优化了，其余的可能更细节了。

Tags: 算法