三个数组三数和问题思考（双指针）

题目：之前介绍过在一个数组上的三数和问题，根据排序后的单调性，我们可以利用双指针来寻找到三个数和为k的三元组，对于四元组实际上多一维进行枚举（四数和问题），这里还有个hash表的解法。那么，回归三数和问题，如果三个数分别处在三个数组中呢？所求的三元组要处于三个数组。

思路：我们同样用双指针的思路：

• 首先我们要对三个数组排序
• 接着枚举A数组构造$k=answer-A[s]$
• 内层循环两个指针分别处于两个数组中，一个在最前方一个在最后方
• 假设$i$在$B[]$的最后，$j$在$C[]$的最前：
• 如果$B[i]+C[j]>k$，则$i--；$
• 如果$B[i]+C[j]<k$，则$j++；$
• 如果$B[i]+C[j]==k$，则$i--；j++;$

关于这样做的原因我们可以分析一下：假如$B[i]+C[j]>k$，说明此时必须要让两个元组的减小，能减小的途径就是$i--$，反之同理。这个题目和在一个从左到右、从上到下分别递增的矩阵中搜索某一个数的思路异曲同工，都是构造能够保证两个决策方向的搜索方式，一个方向递增，另一个方向递减。到此，本题就解决了