共计 1709 个字符，预计需要花费 5 分钟才能阅读完成。
一、前言
本篇次要介绍双指针技巧的第二类题型：对数组进行预处理之后，再采纳双指针遍历。
在 Medium 难度的题目中，此类问题能够演绎为 K-Sum 问题：
- 两数之和：【881. 救生艇】；
- 三数之和：【16. 最靠近的三数之和】、【15. 三数之和】、【923. 三数之和的多种可能】；
- 四数之和：【18. 四数之和】；
二、881. 救生艇
第 i 集体的体重为 people[i]，每艘船能够承载的最大分量为 limit。每艘船最多可同时载两人，但条件是这些人的分量之和最多为 limit。返回载到每一个人所需的最小船数。(保障每个人都能被船载)。
由题意可知，保障所需的最小船数，意味着每一趟尽可能地搭载两个人，并且他们的分量最靠近最大分量，以便后续趟次可能组成两个人。
解题的要害就在于 每趟尽可能地从数组中找出和值小于最大分量的最大值最小值的二元组。
那么对数组排序预处理之后，能够很容易地从左侧找到最小值，右侧找到最大值，双指针再向两头遍历，即可解题。
三、16. 最靠近的三数之和
给定一个包含 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最靠近。返回这三个数的和，假设每组输出只存在惟一答案。
奢侈解法就是通过三层循环枚举各种排列状况来找到最靠近的和值，工夫复杂度为 O(n^3)。
这里能够利用 降维思维，将其转化为两数之和的问题，那么解题思路和【881. 救生艇】一模一样：
工夫复杂度被升高为 O(nlogn+n^2)。
四、15. 三数之和
给定一个蕴含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c，使得 a + b + c = 0？找出所有满足条件且不反复的三元组。
有了上述题目的铺垫，再看本题，是不是会浮现以下解题范式：
- 降维思维，将三数之和转化为两数之和的问题；
- 对数组进行排序，将双循环问题转化为单循环问题；
对于不反复三元数组这一条件，同学们第一工夫可能会想到采纳 HashTable 来去重，然而整个双指针解题的过程中，三个数始终保持着非递加序列的个性，那么遇到反复数字间接跳过即可：
参考视频：传送门
五、923. 三数之和的多种可能
给定一个整数数组 A，以及一个整数 target 作为目标值，返回满足 i < j < k 且 A[i] + A[j] + A[k] == target 的元组 i, j, k 的数量。
1、双指针解法
本题的难度在于：含有反复数字时，双指针无奈残缺地统计出两数之和的所有排列。
以数组 [2, 2, 6, 6] 为例，寻找和值为 8 时，无论你怎么设置双指针的挪动规定，只能得出两组和值为 8 的组合，所以对于反复元素就必须得利用排列组合相干的数学知识来解决。
依然以和值 8 为例，会有如下两种状况：
- 如果数组的模式为 [2, 2, 6, 6]，那么排列组合数就是 2 * 2；
- 如果数组的模式为 [4, 4, 4, 4]，那么排列组合数就是 4 * 3 / 2（4 个中取 2 个）；
那么寻找到满足条件的和值之后，还须要将双指针再次向前挪动，找出相应的个数，来计算其组合数：
从上述代码中能够发现计算反复数组合的局部非常复杂。
2、数学方法 — 组合
当初，同学们能够尝试 逆向思维：枚举所有和值为目标值的三元组，那么只有晓得三元组中的数字在数组 A 中的数量，即可计算出组合数。
相比拟数组 A 的长度，target 则小很多，那么工夫复杂度能够大大地升高为 O(n+target^2)，另外须要 O(n) 的空间复杂度来存储数组 A 中数字的个数。
六、18. 四数之和
给定一个蕴含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不反复的四元组。
了解【15. 三数之和】的解题思路之后，这道题目实质上的区别就是多了一个循环。
写在最初
算法作为计算机的基础学科，用 JavaScript 刷，一点也不丢人 ε =ε=ε=┏(゜ロ゜;)┛。
本系列文章会别离给出一种算法的 3 种难度的总结篇（简略难度，中等难度以及艰难难度）。在简略难度中，会介绍该算法的基本知识与实现，另外两个难度，着重解说解题的思路。
如果本文对您有所帮忙，能够点赞或者关注来激励博主。