算法训练营第十四天| 18.四数之和

题目链接：https://leetcode.cn/problems/4sum/ 视频讲解：https://www.bilibili.com/video/BV1DS4y147US

核心思路：

外层套两层 for 循环固定 nums 【k】与 nums 、【i】，用 left、right 指针向中间移动，寻找四数之和等于 target 的组合

自己看到题目的第一想法

看到题目是在单个数组中找出和为 target 的不重复四元组，第一反应这是三数之和的升级版，核心思路一定是排序 + 双指针。

因为要求不重复，所以必须先排序，方便后续去重。

思路：固定前两个数，用双指针指向后两个数，通过调整指针找到和为 target 的组合，同时全程做去重。

一开始担心四层循环超时，所以坚定用双指针把复杂度降到 O(n³)，完全能通过 n=200 的数据。
实践代码如下：

今日收获：

- 两数之和：哈希表（快速查找）

- 三数之和、四数之和：排序 + 双指针（去重方便）

- n 数之和：都可以用“固定前 n-2 个数 + 双指针”解决