本文共 645 字，大约阅读时间需要 2 分钟。

写在前面的话

最近在刷LeetCode的时候，遇到了KSum问题。这里就总结一下，以防自己以后忘记了。 首先，KSum涉及的问题大部分是2Sum、3Sum、4Sum，这里举例说一下2Sum和3Sum。 2Sum 1、先将拿到的数值排序 2、逐个取出小于等于0的数，然后在该数的右边查找，是否存在一个数，等于它的相反数。

3Sum

1、先将拿到的数值排序 2、逐个取出小于等于0的数，然后在该数的右边设置两个指针，头指针指向右边第一个数，尾指针指向最后一个数。然后比较两个指针相加的和是否等于该数的相反数。

KSum问题的总结

这是有人总结的，个人觉得有点问题，不知道是不是我理解不到位。举个例子，4Sum。 计算所有的两个数的和，存在一个有序数组S中，然后查看S是否存在一对相反数。 如果输入的数组是{-4，-1，1，0，4}时，我们知道（-4，-1，1，4）是符合的，但是，我们在计算输入数组中的两两之和时，结果是{-5，-4，-3，-1，0，0，1，3，4，5}，那么-4和4这对相反数，对应的数是（-4，0）和（0，4），可是这样的结果只有3个元素。所有个人觉得有问题。

这里我觉得当问题遇到瓶颈的时候，递归会是一种不错的选择。

1、先将输入的数组进行排序 2、逐个取出一个个数x，这里是N。 3、然后要做的就是寻找(K-1)Sum问题，并且相加之和是-x； 4、递归下去，最后就是查找2Sum，记住这里2Sum是两个指针一前一后扫描，所以也是N。所以最后的时间复杂度是N^(k-1)