☆打卡算法☆LeetCode 18、四数之和 算法解析

> 推荐阅读

>

> - CSDN主页

> - GitHub开源地址

>- Unity3D插件分享

> - 简书地址

> - 我的个人博客

> - QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

## 一、题目

### 1、算法题目

“给定一个整数数组和目标值，返回满足条件的四元数组。”

题目链接：

来源：力扣（LeetCode）

链接：18. 四数之和 - 力扣（LeetCode） (leetcode-cn.com)

### 2、题目描述

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] ：

- 0 <= a, b, c, d < n

- a、b、c 和 d 互不相同

- nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

```

示例 1：

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

输出： [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

```

```

示例 2：

输入： nums = [2,2,2,2,2], target = 8

输出： [[2,2,2,2]]

```

## 二、解题

### 1、思路分析

这道题跟三数之和有些类似，解法也有点类似，暴力解法就是四重循环遍历所有的四元组，然后用哈希表去重，找到不重复的四元组就是最终答案，但是四重循环的时间复杂度是O(N⁴)，去重的时间复杂度和空间复杂度也比较高，需要换一种思路。

本题可以三数之和题目的解法基础上加一层循环，然后使用双指针的解法。

### 2、代码实现

首先对整数数组进行排序，然后两层循环遍历数组中所有的整数，代码参考：

```csharp

public class Solution {

​ public IList<IList<int>> FourSum(int[] nums, int target) {

​ IList<IList<int>> resultList=new List<IList<int>>();

​ int Length=nums.Length;

​ if(nums==null||Length<4) return resultList;

​ Array.Sort(nums);

​ for(int i=0;i<Length;i++){

​ if(i>0&&nums[i]==nums[i-1]) continue;//去重

​ for(int j=i+1;j<Length;j++){

​ if(j>i+1&&nums[j]==nums[j-1]) continue;//去重

​ int L=j+1;

​ int R=Length-1;

​ while(L<R){

​ int sum=nums[i]+nums[j] + nums[L] + nums[R];

​ if(sum==target){

​ resultList.Add(new List<int>{nums[i],nums[j],nums[L],nums[R]});

​ while(L<R&&nums[L]==nums[L+1]) L++;//去重

​ while(L<R&&nums[R]==nums[R-1]) R–;//去重

​ L++;

​ R–;

​ }

​ else if(sum>target) R–;

​ else if(sum<target) L++;

​ }

​ }

​ }

​ return resultList;

​ }

}

```

### 3、时间复杂度

时间复杂度 ： O(N³)

其中 n 是数组的长度。排序的时间复杂度是 O(n log n)，枚举四元组的时间复杂度是 O(n³)，因此总时间复杂度为 O(n³ +n log n)=O(n³ )。

空间复杂度： O(log n)

其中 nn 是数组的长度。空间复杂度主要取决于排序额外使用的空间。此外排序修改了输入数组 nums，实际情况中不一定允许，因此也可以看成使用了一个额外的数组存储了数组 nums 的副本并排序，空间复杂度为 O(n)。

## 三、总结

使用上述解法，在枚举所有的四元组的时候，仍然使用的四重循环，所以时间复杂度为O(n⁴)，但是已经对数组进行过排序，因此可以使用双指针方法去掉一重循环，让时间复杂度降为O(n³)。

使用两重循环分别枚举前两个数，然后在两重循环枚举到的数之后使用双指针枚举剩下的两个数。