XSUM-从数组中X个元素，使得它们的和为target的问题总结

分手后的思念是犯贱 2024-04-17 20:57 41阅读 0赞

XSUM问题：即从数组中找出X个元素，使得这些元素的和为某个给定的target，每个元素只能使用一次。其中  x ≥ 2 x\\geq 2 x≥2

这类问题的通用解法如下：

1.  将数组  n u m s nums nums 排序，排序的目的 一方面利于去重，另外一方面利于遍历,设数组长度为  n n n。
2.  写一个X-2 重的循环，每一层循环表示 这前X-2个数字的遍历过程，而且内层循环的循环变量  i n d e x j index\_\{j\} indexj 要大于外层循环（防止重复）的循环变量 i n d e x i index\_\{i\} indexi
3.  最里层的循环体就用于解决最后两个数。设最后两个数的下标为 l e f t , r i g h t left,right left,right,这两个的数遍历方式如下:
    
     *  让  l e f t left left 从  1 + i n d e x x − 2 1+index\_\{x-2\} 1\+indexx−2开始往后遍历，越往后  n u m s \[ l e f t \] nums\[left\] nums\[left\] 会越大。
     *  让 r i g h t right right从 n − 1 n-1 n−1 开始往前遍历，越往前 n u m s \[ r i g h t \] nums\[right\] nums\[right\] 会越小
     *  对于每一次的 l e f t , r i g h t left,right left,right，计算此时产生的X个数的和 sum，如果这个sum小于target,将left增大，如果sum大于target 将right增大。如果sum==target说明找到了答案，此时做答案的处理。
     *  当sum==target的时候，如果是想要寻找所有不重复的组合方式，那么需要继续寻找，此时需要做去重工作，让left一直增，直到得到新的数；让right一直减直到得到新的数，
4.  外层的每层循环的末尾，加上对这个循环变量的去重，即跳过与当前数字相同元素。

时间复杂度： O ( n X − 1 ) O(n^\{X-1\}) O(nX−1)  
题目：

两个数的和： https://blog.csdn.net/jmh1996/article/details/100177089 , 输出下标。X=2,target不固定。  
三个数的和为0：https://blog.csdn.net/jmh1996/article/details/100174774 ，输出所有可能的不重复的组合，X=3,target=0的题。  
三个数的最靠近某个target的和：https://blog.csdn.net/jmh1996/article/details/100174532

四个数的和：https://blog.csdn.net/jmh1996/article/details/100175808