18. 四数之和 [medium]

18. 四数之和 [medium]

https://leetcode-cn.com/problems/4sum/

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

• 答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：

[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

通过次数92,910 | 提交次数244,289

Second Try

2020-07-22

按照标准解法来一波，所谓的双指针其实也就最后一个内循环的left和right进行双边向内移动而已，外面的依然是两轮循环，也没什么特别。复杂度从暴力解法的O(n^4)变成O(N^3), 不过再加上一些提前终止的条件，其实是更快的。

为了避免重复，也对每层元素下一轮迭代进行了判断，这样最后就不用转化为set处理了。

有个容易出bug的地方，当要判断不与上一个相同的时候，判断j不能直接用nums[j] ==nums[j-1]，而应该考虑上j > i + 1, 代表该轮循环已经走过一步了。不然nums[j]都不能等于nums[i]，就是一个bug了。

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        # 使用经典双指针算法
        nums = sorted(nums)
        n = len(nums)
        rv = []
        # i < j < p <q, 但是nums[i] <= nums[j] <= nums[p] <= nums[q]
        for i in range(n-3):
            if 4 * nums[i] > target:  # 以后只会越来越大，没希望了
                break 
            if nums[i] + 3 * nums[-1] < target:  # 这一轮没希望了，但下一步会更大，还有希望
                continue 
            # 减少重复
            if i > 0 and nums[i] == nums[i-1]:
                continue 

            # three's sum环节
            for j in range(i + 1, n-2):
                if nums[i] + 3 * nums[j] > target:
                    break 
                if nums[i] + nums[j] + 2 * nums[-1] < target:
                    continue 
                # 减少重复
                # wtf, 又是一个bug
                # if nums[j] == nums[j-1]:
                #     continue 
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue 

                p, q = j + 1, n - 1
                while p < q:
                    tmp_s = nums[i] + nums[j] + nums[p] + nums[q]
                    if tmp_s < target:
                        p += 1
                    elif tmp_s > target:
                        q -= 1
                    else:
                        rv.append([nums[i], nums[j], nums[p], nums[q]])
                        p += 1
                        q -= 1
                        # 去重重复的可能
                        while nums[p] == nums[p-1] and p < q:
                            p += 1
                        while nums[q] == nums[q+1] and p < q:
                            q -= 1
        return rv 
                

• 执行用时：120 ms, 在所有 Python3 提交中击败了79.53%的用户
• 内存消耗：13.5 MB, 在所有 Python3 提交中击败了6.52%的用户

First Try

2020-07-22

优化的暴力解法, 没有按照所谓的双指针经典解法来写，毕竟没经验没想到。。。

基本上是通过测试案例来补全的，一是判断往后轮询一定大于target；二是判断当前配置加上最大值小于target。前者是跳过整个循环，后者只是跳过当前step，寻找更大的下一个step。后者的debug花费了很多时间，按照思路套路以为都是break, 又是一个bug.

这个解法直观容易理解。

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)
        nums = sorted(nums)
        rv = set()
        for i in range(n-3):
            if 4 * nums[i] > target: # 有可能后面的数字都相等，因此是大于号，而不是大于等于
                break
            if nums[i] + nums[-1] * 3 < target:
                continue  # continue 而非break,毕竟后面的i可以更大 
            for j in range(i+1, n-2):
                if nums[i] + 3 * nums[j] > target:
                    break
                if nums[i] + nums[j] + nums[-1] * 2 < target:
                    continue 
                for p in range(j+1, n-1):
                    if nums[i] + nums[j] + 2 * nums[p] > target:
                        break
                    if nums[i] + nums[j] + nums[p] + nums[-1] < target:
                        continue # continue而非break.. 
                    for q in range(p+1, n):

                        if nums[i] + nums[j] + nums[p] + nums[q] == target:
                            rv.add((nums[i], nums[j], nums[p], nums[q]))
                        elif nums[i] + nums[j] + nums[p] + nums[q] > target:
                            break
        rv = [list(e) for e in rv]
        return rv 

• 执行用时：632 ms, 在所有 Python3 提交中击败了59.37%的用户
• 内存消耗：13.7 MB, 在所有 Python3 提交中击败了6.52%的用户

• 暴力解法超时

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)

        nums = sorted(nums)
        rv = set()
        for i in range(n-3):
            for j in range(i+1, n-2):
                for p in range(j+1, n-1):
                    for q in range(p+1, n):
                        if nums[i] + nums[j] + nums[p] + nums[q] == target:
                            rv.add((nums[i], nums[j], nums[p], nums[q]))
        rv = [list(e) for e in rv]
        return rv