力扣18题 四数之和：从基础到精通，一篇文章带你突破算法难关

作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。

会一些的技术：数据分析、算法、SQL、大数据相关、python

欢迎加入社区：码上找工作

作者专栏每日更新：

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化：企业实战案例

备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级

引言

力扣第18题，也称为“四数之和”，是一道中等难度的算法题目。它扩展自经典的两数之和和三数之和问题，要求在一个数组中找出所有不重复的四元组，这些四元组的和等于给定的目标值。

问题描述

给你一个由 n 个整数组成的数组 nums 和一个目标值 target，请你找出并返回满足以下条件的不重复四元组：

• 四元组中的每个元素都是数组 nums 中的元素。
• 四元组的和等于 target。
• 答案中不可以包含重复的四元组。

输入: nums = [1, 0, -1, 0, -2, 2], target = 0
输出: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

解释

这个输入例子中的数组 nums 包含六个整数 [1, 0, -1, 0, -2, 2]，目标值 target 是 0。按照题目要求，我们需要找出所有唯一的四元组，使得它们的和为 0。

对于给定的输入，有三个不重复的四元组的和为 0：

1. 四元组 [-2, -1, 1, 2]：这四个数的和为 -2 + (-1) + 1 + 2 = 0
2. 四元组 [-2, 0, 0, 2]：这四个数的和为 -2 + 0 + 0 + 2 = 0
3. 四元组 [-1, 0, 0, 1]：这四个数的和为 -1 + 0 + 0 + 1 = 0

这些四元组满足题目的所有条件，包括它们的和等于 0，且在答案中不包含重复的四元组。

算法比较

与两数之和和三数之和类似，四数之和可以通过双指针法求解，但其复杂度相对较高。主要算法思想是先排序，然后使用两层循环固定前两个数，用双指针移动来确定后两个数。

详细算法解释和策略

1. 排序：首先对数组进行排序，这是后续双指针法的基础。
2. 双层循环：外层循环从头开始遍历数组，用于固定第一个数；内层循环从外层循环的下一个位置开始，用于固定第二个数。
3. 去重：为了避免重复的四元组，当我们在固定数的循环中遇到相同的值时，需要跳过继续执行。
4. 双指针：在每一对固定数的基础上，使用左右指针在剩余数组中寻找两个数，使得这四个数的和等于 target。如果和小于 target，移动左指针；如果和大于 target，移动右指针。
5. 记录结果：每当找到一组满足条件的四元组时，记录下来，并继续尝试寻找下一组。

代码示例

python
def fourSum(nums, target):
    nums.sort()
    result = []
    n = len(nums)
    for i in range(n):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        for j in range(i+1, n):
            if j > i+1 and nums[j] == nums[j-1]:
                continue
            left, right = j+1, n-1
            while left < right:
                total = nums[i] + nums[j] + nums[left] + nums[right]
                if total == target:
                    result.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
                elif total < target:
                    left += 1
                else:
                    right -= 1
    return result

算法分析

时间复杂度：O(n^3)，主要时间消耗在双层循环和双指针搜索上。

空间复杂度：O(logn)到O(n)，取决于排序算法的空间复杂度。

算法改进

针对力扣第18题“四数之和”的基本算法已经相对优化，主要采用排序加双指针的方法来减少不必要的搜索。然而，在实际应用中，还有一些改进策略可以进一步提高算法的效率：

1. 预先检查：在进入四重循环之前，可以先做一些预先检查来剪枝。
   • 如果数组已排序，检查最小的四个数的和是否大于target，或者最大的四个数的和是否小于target。如果是，那么可以直接返回空列表，因为不存在合法的四元组。
   • 类似地，进入每一层循环时，都可以做这样的检查，比如在固定第一个数之后，检查这个数与最大的三个数的和是否小于target，以此类推。
2. 跳过重复元素：在寻找四元组的过程中，如果两个连续的数相同，可以跳过后面的数，以避免重复计算和返回重复的四元组。这一步在循环的每一层都很有用。
3. 哈希表辅助：除了双指针方法，还可以考虑使用哈希表来存储两数之和，以减少查找时间。具体来说，可以先遍历数组，用哈希表存储所有可能的两数之和，以及这两个数的索引。然后，再通过查找哈希表中是否存在两个和为target的键值对来找到四元组。这种方法可能需要额外处理来避免重复的四元组。
4. 多指针策略：在某些情况下，可以尝试将双指针法扩展到更多指针，例如在固定了前两个数之后，使用双指针来确定后两个数。虽然这不会改变算法的时间复杂度，但是在某些特定情况下可以减少不必要的迭代，尤其是当数组中存在多个相同的元素时。
5. 并行计算：考虑到四数之和的问题可以分解为多个子问题，可以尝试使用并行计算来同时解决这些子问题。例如，可以并行地执行对不同子数组的搜索。不过，这种方法需要注意线程同步和数据一致性问题。

改进后代码

def fourSum(nums, target):
    nums.sort()  # 对数组进行排序
    n = len(nums)
    result = []
    # 预先检查
    if n < 4 or sum(nums[:4]) > target or sum(nums[-4:]) < target:
        return result
    for i in range(n - 3):
        # 跳过重复的第一个数
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        # 在剩余的范围内最小的三个数之和加上当前数如果大于target，后面就不可能了
        if sum(nums[i:i+4]) > target:
            break
        # 当前数与最大的三个数之和如果小于target，当前数太小，继续
        if nums[i] + sum(nums[-3:]) < target:
            continue
        for j in range(i + 1, n - 2):
            # 跳过重复的第二个数
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue
            # 类似上面的剪枝操作
            if sum(nums[j:j+3]) > target - nums[i]:
                break
            if nums[j] + sum(nums[-2:]) < target - nums[i]:
                continue
            left, right = j + 1, n - 1
            while left < right:
                total = nums[i] + nums[j] + nums[left] + nums[right]
                if total == target:
                    result.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
                elif total < target:
                    left += 1
                else:
                    right -= 1
    return result

这个版本的代码通过在循环开始前进行一些简单的预检查来剪枝，减少不必要的迭代。此外，它还在内循环中使用了跳过重复元素的策略，以避免生成重复的四元组。

注意，尽管我们通过这些策略提高了效率，但这个问题的时间复杂度仍然是O(n^3)，这是由于我们需要三层嵌套循环来寻找所有可能的四元组组合。然而，这些优化可以在实际应用中对执行时间产生显著影响，尤其是在处理包含大量重复元素的大数组时。

图解算法

我们的输入是nums = [1, 0, -1, 0, -2, 2]，目标值target = 0。经过排序后的数组为[-2, -1, 0, 0, 1, 2]。

应用场景

四数之和问题在数据分析、金融工程等领域中有广泛的应用，特别是在需要从大量数据中寻找特定数值组合的场景。

图解说明

步骤1：以-2为第一个固定数，-1为第二个固定数，左指针指向0（索引2），右指针指向2（索引5）。这时四数之和为-1，不满足条件。

步骤2：保持-2和-1不变，左指针向右移动到另一个0（索引3），此时四数之和为0，符合条件，记录这个四元组[-2, -1, 0, 2]。

步骤3：改变固定的第二个数为0（索引2），左指针位于0（索引3，但实际上在这一轮中不会移动到这里，因为它是重复的），右指针仍然指向2，四数之和再次为0，记录四元组[-2, 0, 0, 2]。

步骤4：固定数变为-1和0（索引1和2），左指针移动到1（索引4），右指针保持在2，四数之和为2，不满足条件。

结论

四数之和是一道典型的数组和双指针使用题目，通过对数组的排序、双层循环和双指针技巧的综合应用，可以有效地解决这个问题。尽管它的时间复杂度较高，但在实际应用中，通过优化去重逻辑和细节处理，可以在一定程度上提高算法的执行效率。

欢迎关注微信公众号 数据分析螺丝钉