18题四个数的求和

发表于 | 更新于 | 分类于
本文字数： 2.6k | 阅读时长 ≈ 2 分钟

四个数的和

难度：中等 思路：头尾逼近法

一、问题描述

给定一个包含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]]

二、问题分析

在LeetCode的题目顺序有一个由浅入深的过渡，这题的解决方法完全可以参照三个数的求和问题。让我们来回顾一个三个数的求和问题，三个数的求和与四个数的求和表面上是一模一样的，无非是把三个数替换为四个数，所以在解决方式上内核机制也是相同的。

2.1 排序

数的求和问题，最简单粗暴的方法就是把给定的数组for循环遍历几次，找到所有符合要求的数，但是因为时间开销过大，提交的时候不被通过，所以只能找其他的渠道。第一步，将所给的数按照从小到大排序，Python有内置的排序函数，这里就直接调用了。

2.2 开始遍历

在多个数求和问题中，使用的方法为两头法，具体实现方法如下。首先固定第一个数，从数组的头部开始，求出目标数target与第一个数的差值diff；然后固定第二个数，求出之前的差值diff与当前数的差值作为新目标goal；然后使用头尾法，如果头尾的和小于goal，则头往后移，如果头尾的和大于goal，则尾往前移（经过排序后，尾部的数大头部的数小），如果头尾的和正好等于goal，那么我们找到了目标数，把四个数存到结果中，同时往中间移动头尾的坐标，头尾位置下标相等时此次遍历结束；然后依次移动前两个固定的数。

2.3 难点分析

这题确定了算法，还是有很多细节需要推敲，而这些细节有些时候比算法本身更花时间。在题目描述中，它特地提出让我们注意解决重复元素的问题，解决重复问题有两个思路：一是处理返回的数组，将其中重复的元素去掉；二是从源头上解决问题，在生成结果数组时，一旦发现重复就不再添加入返回数组。这题真正的难点就在这里了，怎么样才能最有效的去除重复元素呢？这里只提供一个巧妙的思路，重复的元素从何而来，归根结底是因为数组中本身就有重复的元素，在求和的时候，当我们移动到下一个元素的时候，检测当前元素与上一个元素是否相等，这里为什么是与前一个元素作比较而不是与后一个元素作比较，这是有原因的，如果与后一个元素作比较的话，那么就会漏掉一种情况，这两个数相等但是他们的和就是我们想找的，如果与后一个元素作比较的话这个数还没有参与计算就会被跳过。结果会错误。（注意，当我们访问一个元素的时候要确保这个元素存在否则就会报错），如果相等就跳过此次循环。（需要确保每个不重复元素都被访问到）

2.4 细节

首先要对输入的数组进行长度判断，避免输入空数组时后续进行不存在位置的的访问导致程序崩溃；其次是重复元素的问题，在元素移动过程中，为了不产生重复的四个数组合，固定的第一个数往后移动时，需要考虑当前数与上一个数是否相等，如果相等，则使用continue语句跳过此次循环。固定的第一个数也存在一模一样的问题。其次是首尾移动时，当检测到首尾之和相等时，头部和尾部的位置都往中间移，这时头尾分别与后一个数作比较，如果相等的话，头尾坐标继续往中间靠。（这里检测到头尾之和与目标相等时，不存在一个数还没用到就被丢弃，所以可以与后一个数作比较）

三、代码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def fourSum(self, nums, target):
    res=[]
    nums=sorted(nums) #排序
    length=len(nums)
    if length < 4:
        return res
    for i in range(0, length-3):
        diff=target-nums[i]
        if i >0 and nums[i-1] == nums[i]: #防止重复
            continue
        for j in range(i+1, length-2):
            goal=diff-nums[j]
            front=j+1
            back=length-1
            if j >i+1 and nums[j-1] == nums[j]:#防止重复
                continue
            while front<back:
                the_sum=nums[front]+nums[back]
                if the_sum < goal:
                    front += 1
                if the_sum > goal:
                    back -= 1
                if the_sum == goal:                        
                    res.append([nums[i], nums[j], nums[front],nums[back]])
                    while front <back and nums[front] == nums[front+1]:#防止重复
                        front+=1
                    while front < back and nums[back]==nums[back-1]:#防止重复
                        back -=1
                    front += 1
                    back -= 1

    return res

复杂度分析：

耗时还是非常多的，排序+O(N^3^)。