LeetCode Prob.15 3Sum的各种解法

作者: Ricolove | 来源:发表于2019-02-27 12:24 被阅读26次

LeetCode Prob.15 3Sum的各种解法
15+18、3Sum 4Sum
数组
Leetcode - Array [持续更新]
15. 3Sum
【哈希法-3sum】3sum
15. 三数之和
15.三数之和
LeetCode算法题-15. 三数之和（Swift）
leetcode 15 - 三数之和

题目描述

给定一个整数列表，请问能否从中找出所有满足a + b + c = 0的三元组？
例如，给定[-1, 0, 1, 2, -1, -4]，那么答案为[[-1, 0, 1], [-1, -1, 2]]。

从2Sum说起

我们看一个简化的问题：如果给定整数列表中，有且仅有一个 a + b = 0 的二元组，那么该怎么求这个a和b呢？

思路很简单：我们设置一个字典，字典的key代表待寻找的数，key和value对应为二元组。

那么接下来，我们只需要遍历整个列表。对于遍历到的数num：

如果num在字典里，那就找到了。

否则，我们令key为0 - num，value为num。

于是代码就是：

class Solution:
    def twoSum(self, nums, target):
        d = {}
        nlen = len(nums)
        i = 0
        while i != nlen:
            if nums[i] in d:
                return [d[nums[i]],i]
            else:
                d[target - nums[i]] = i
                i += 1

基于2Sum的3Sum

有了2Sum的铺垫，只需要找到把3Sum问题转化为2Sum问题的方法就好了。这个方法的思想是这样的：

首先，我们对整数列表nums进行排序。这可以帮助我们简化思路。
然后，遍历nums。
我们设遍历到的位置为fixpt。那么，现在的任务就是，在 fixpt + 1 到 len(nums) - 1 这个区间内，寻找到 a + b = 0 - nums[fixpt] 的二元组就可以了。

先来看看代码：

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        #无解的情况有三个：元素个数不足，元素都大于或小于0。所以可以直接返回空列表。
        if len(nums) < 2 or nums[0] > 0 or nums[-1] < 0: return []

        ans = []
        fixpt = 0
        nlen = len(nums) 

        while fixpt < nlen - 2:
            #这里是两个简化条件：
            #第一，如果fixpt指向的数都大于0了，那么剩下的数肯定都大于0了
            #第二，当我们在当前的fixpt搜索完毕，那么也就是fixpt+1到nlen的所有解都被我们搜索完了。
            #因此，如果fixpt+1指向的数和fixpt的相等，那么fixpt+2到nlen的可行解
            #当然也已经被fixpt时的搜索找到了。
            #所以才可以有这个直接跳过的步骤。
            if nums[fixpt] > 0: break
            if fixpt > 0 and nums[fixpt] == nums[fixpt - 1]:
                fixpt += 1
                continue

            mpt = fixpt + 1
            d = {}
            qd = {}
            #d的作用和2Sum时一样。
            #qd的作用是为了省去查找解重复的时间。
            while mpt != nlen:
                mptn = nums[mpt]
                #下面这个if就是在判断当前数是否为d的key了。
                if mptn in d and (nums[fixpt],mptn) not in qd:
                    ans.append([nums[fixpt], d[mptn], mptn])
                    qd[(nums[fixpt],mptn)] = True
                #而这个if则是添加key。
                elif 0 - nums[fixpt] - mptn not in d:
                    d[0 - nums[fixpt] - mptn] = mptn
                mpt += 1
            fixpt += 1
        return ans

总的核心就在最后那部分。前面的部分大多是简化时间的。

最终，LeetCode上运行的时间大约在1200+ms。

双指针法对可行解搜索的简化

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        if len(nums) == 0 or nums[0] > 0 or nums[-1] < 0: return []

        ans = []
        pt = 0

        while pt < len(nums) - 2: 
            if nums[pt] > 0: break
            if pt > 0 and nums[pt] == nums[pt - 1]:
                pt += 1
                continue

            left = pt + 1
            right = len(nums) - 1
            while left < right:
                if nums[pt] + nums[left] + nums[right] == 0:
                    ans.append([nums[pt], 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
                elif nums[pt] + nums[left] + nums[right] > 0:
                    right -= 1
                else:
                    left += 1
            pt += 1
        return ans

在这个算法中，前面的简化部分依然没有什么变化，但是在可行解搜索的部分，用了速度更快的双指针法。

它的思想是这样的，首先fixpt这里改叫pt，依然是一个定点，用来提供2Sum查找的目标。

但是，现在有两个指针，left和right，从两边逐渐往中间缩，根据查找到的三数和决定是移动left还是移动right。

具体到代码上，缩的策略是这样的：

while left < right:
    # 若满足了a+b+c=0的条件，那么当然就记录答案了
    if nums[pt] + nums[left] + nums[right] == 0:
        ans.append([nums[pt], nums[left], nums[right]])
        #这里指针的再次移动是很关键的，不能用break代替
        #因为可行解可能不止一个，在内部还可能有别的可行解，所以跳过同类数字后再次进入大循环查找。
        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
    #如果a+b+c>0，那么说明nums[left] + nums[right]的总和偏大，所以应当减小大数，即right -= 1。
    elif nums[pt] + nums[left] + nums[right] > 0:
        right -= 1
    #同样的道理，只不过是为了让总和增大。
    else:
        left += 1

最后调整总和大小还好理解，但是那两行while是用来干什么的呢？

举个例子，就是[-1, 0, 1, 2, -1, -4]吧。排序之后，这个列表是[-4, -1, -1, 0, 1, 2]。-4显然没有对应项，但是对于第一个-1，在这个算法下，第一个找到的可行解是[-1,-1,2]。然而，如果就这么break了，就会丢失[0, 1]这个部分的搜索，而这部分恰恰是和-1能组成可行解。

这个算法的时间大概是1000ms+。

正负数配对

在定点的思想下，暴力一点的解法就是在定点之后的搜索区间内进行配对了。这样的方法肯定是比优化过的方法慢一些的，因为这已经接近n^2了，而双指针只需要n的时间。

然而，这种n^2的配对用得好的话，效果也是不错的。我们可以分析一下这个问题：要满足a + b + c = 0，需要满足什么条件？

如果没有0或者有一个数是0，那么必然需要有两个数一正一负。
如果有两个数是0，那么第三个也必须是0。

由此我们可以构思，如果我们将正数、负数、0分别归入集合，并对数字进行计数处理，那么就可以这么做：

若0的个数大于2，那么可行解必然有[0, 0, 0]。
我们从正数和负数中各取一个数，然后计算我们的目标，比如说，取了x和y两个数，那么需要寻找的就是s = -(x + y)。
- 有可能s == x or s == y。不妨设s == x，那么只要看x的个数是否大于1，若如此，则有可行解[x, x, y]。对于s == y的情况也类似。
- 如果不等，那么我们只需要在x < s < y的时候，以[x, s, y]作为我们的可行解。因为，接下来的配对，可能会选到数对s和y，那么再计算的时候，x就成了我们的目标。既然三个数必然存在x < s < y关系，那么我们就只在这个关系满足的时候视为可行解，这样就避免了重复添加可行解的麻烦。

分析完了，代码是这样的：

class Solution:
    def threeSum(self, nums):
        d = {}
        for val in nums:
            d[val] = d.get(val, 0) + 1
        
        pos = [x for x in d if x > 0]
        neg = [x for x in d if x < 0]
        
        res = []
        if d.get(0, 0) > 2:
            res.append([0, 0, 0])
            
        for x in pos:
            for y in neg:
                s = -(x + y)
                if s in d:
                    if s == x and d[x] > 1:
                        res.append([x, x, y])
                    elif s == y and d[y] > 1:
                        res.append([x, y, y])
                    elif y < s < x:
                        res.append([x, y, s])
        return res

这里的一个巧妙的操作细节是，先用字典得到所有不重复的数字，以及出现的次数。然后就很好处理了。

既简捷又快速。这个LeetCode的样例得分是320ms。

任意值3Sum算法的特殊情况

在LeetCode上最快的解法，有很多数字技巧，有些地方我也没琢磨透。具体是这样的：

class Solution:
    def threeSum(self, nums: 'List[int]') -> 'List[List[int]]':
        from bisect import bisect_left, bisect_right
       
        target = 0
        
        result = []
        length = len(nums)
        
        if length < 3:
            return result
        
        count ={}
        # map the counts
        for n in nums:
            if n in count:
                count[n] += 1
            else:
                count[n] = 1
            
        keys = list(count.keys())
        keys.sort()
      
        t3 = target // 3
        if t3 in keys and count[t3] >= 3:
            result.append([t3, t3, t3])

        begin = bisect_left(keys, target - keys[-1] * 2)
        end = bisect_left(keys, target * 3)

        for i in range(begin, end):
            a = keys[i]
            if count[a] >= 2 and target - 2 * a in keys:
                result.append([a, a, target - 2 * a])

            max_b = (target - a) // 2  # target-a is remaining
            min_b = target - a - keys[-1]  # target-a is remaining and c can max be keys[-1]
            b_begin = max(i + 1, bisect_left(keys, min_b))
            b_end = bisect_right(keys, max_b)

            for j in range(b_begin, b_end):
                b = keys[j]
                c = target - a - b
                if c in count and b <= c:
                    if b < c or count[b] >= 2:
                        result.append([a, b, c])
        return result

先解释一下，bisect是二分查找库，left和right的含义可以自己查查，很好理解。

首先明确一下，3Sum问题的解一共四类：

[0, 0, 0]，三数相等。
[a, a, b]；
[a, b, b]，以上2和3都有a < b。
[a, b, c]，a < b < c。

下面我们会拿这个序号来指代解的类型。

我们一步步来分析：

        target = 0

这一行就已经表明了这是一个通用的3Sum算法，可以用来算任意target = a + b + c值的3Sum。

然后是计数部分：

        count ={}
        # map the counts
        for n in nums:
            if n in count:
                count[n] += 1
            else:
                count[n] = 1

这里的计数和上面正负配对法的

        d = {}
        for val in nums:
            d[val] = d.get(val, 0) + 1

部分是一样的。

然后代码就有趣起来了：

        keys = list(count.keys())
        keys.sort()
      
        t3 = target // 3
        if t3 in keys and count[t3] >= 3:
            result.append([t3, t3, t3])

为什么要这么算t3呢？我没看懂这里整数除法的意思，不过对于我们target == 0的情况，可以直接简化为0的个数是否大于等于3。也就是，判断第一种解存不存在。

然后就是很巧妙的搜索范围简化：

        begin = bisect_left(keys, target - keys[-1] * 2)
        end = bisect_left(keys, target * 3) #might use target // 3

        for i in range(begin, end):
            a = keys[i]
            if count[a] >= 2 and target - 2 * a in keys:
                result.append([a, a, target - 2 * a])

在这里，我们要规定a，三元组最小数的搜索范围。
begin的查找参数，意味着就算我们用两个最大的数keys[-1]来构成可行解，那么最小的数也只能是target - keys[-1] * 2。
而end的查找参数（我认为这里应该用整数除法，实际上这么改之后也ac了），它意味着最小数的最大值也不能超过t3，不然作为三元组的最小数，三个a相加都已经超出target了。

下一步就是在可行的a中，看看有没有可行的第二种解。

懂了a的范围处理方式之后，b的范围处理自然也好理解了，而且方法也印证了上面说的end参数要用整数除法的修改。

            max_b = (target - a) // 2  # target-a is remaining
            min_b = target - a - keys[-1]  # target-a is remaining and c can max be keys[-1]
            b_begin = max(i + 1, bisect_left(keys, min_b))
            b_end = bisect_right(keys, max_b)

一旦我们确定了a和b，那么c也就自然确定了：

            for j in range(b_begin, b_end):
                b = keys[j]
                c = target - a - b
                if c in count and b <= c:
                    if b < c or count[b] >= 2:
                        result.append([a, b, c])

由于b和c可能在搜索过程中逆序出现，因此我们就用b <= c的方法确定什么时候确定可行解。

最后这里if b < c or count[b] >= 2:的逻辑也有点巧妙，先判断b < c是否成立，如果我们需要判断count[b] >= 2，那么就暗含了 c == b。

前者找出了第四种解，后者找出了第三种解。那么这样，四种可能的解的类型都被我们找完了。

由此整个代码就分析结束，它的条理非常清楚，速度也很快，在最快的情况下可以达到280ms。

4Sum？

这个就留到下次再说了，哈哈~

LeetCode Prob.15 3Sum的各种解法
题目描述给定一个整数列表，请问能否从中找出所有满足a + b + c = 0的三元组？例如，给定[-1, 0, ...
15+18、3Sum 4Sum
15、3Sum Example 复杂度思路解法 18、4Sum Example 解法
数组
数组题目总结 sum类型的题 leetcode 2sum leetcode 15. 3Sum思路：将3sum转化成...
Leetcode - Array [持续更新]
15. 3Sum --- Medium[https://leetcode.com/problems/3sum/]1...
15. 3Sum
15. 3Sum 题目:https://leetcode.com/problems/3sum/ 难度: Mediu...
【哈希法-3sum】3sum
题目链接：leetcode 15 https://leetcode.com/problems/3sum/descr...
15. 三数之和
题目地址(3sum/">15. 三数之和) https://leetcode.cn/problems/3sum/[...
15.三数之和
https://leetcode-cn.com/problems/3sum/
LeetCode算法题-15. 三数之和（Swift）
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/3sum 题...
leetcode 15 - 三数之和
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/3sum[h...