多数之和问题（nSum）

admin1

1. ```C++
2. vector<int> twoSum(vector<int>& nums, int target) {
3.         // 先对数组排序
4.         sort(nums.begin(), nums.end());
5.         // 左右指针
6.         int lo = 0, hi = nums.size() - 1;
7.         while (lo < hi) {
8.             int sum = nums[lo] + nums[hi];
9.             // 根据 sum 和 target 的比较，移动左右指针
10.             if (sum < target) {
11.                 lo++;
12.             } else if (sum > target) {
13.                 hi--;
14.             } else if (sum == target) {
15.                 return {nums[lo], nums[hi]};
16.             }
17.         }
18.         return {};
19. ```

复制代码

1. ```C++
2. vector<vector<int>> twoSumTarget(vector<int>& nums, int target {
3.         // 先对数组排序
4.         sort(nums.begin(), nums.end());
5.         vector<vector<int>> res;
6.         int lo = 0, hi = nums.size() - 1;
7.         while (lo < hi) {
8.             int sum = nums[lo] + nums[hi];
9.             // 根据 sum 和 target 的比较，移动左右指针
10.             if      (sum < target) lo++;
11.             else if (sum > target) hi--;
12.             else {
13.                 res.push采用back({lo, hi});
14.                 lo++; hi--;
15.             }
16.         }
17.         return res;
18.     }
19. ```

复制代码

1. ```C++
2. while (lo < hi) {
3.         int sum = nums[lo] + nums[hi];
4.         // 记录索引 lo 和 hi 最初对应的值
5.         int left = nums[lo], right = nums[hi];
6.         if (sum < target)      lo++;
7.         else if (sum > target) hi--;
8.         else {
9.             res.push采用back({left, right});
10.             // 跳过所有重复的元素
11.             while (lo < hi && nums[lo] == left) lo++;
12.             while (lo < hi && nums[hi] == right) hi--;
13.         }
14.     }
15.     }
16. ```

复制代码

admin1

1. ```C++
2. vector<vector<int>> threeSumTarget(vector<int>& nums, int target) {
3.         // 数组得排个序
4.         sort(nums.begin(), nums.end());
5.         int n = nums.size();
6.         vector<vector<int>> res;
7.         // 穷举 threeSum 的第一个数
8.         for (int i = 0; i < n; i++) {
9.             // 对 target - nums[i] 计算 twoSum
10.             vector<vector<int>>
11.                     tuples = twoSumTarget(nums, i + 1, target - nums[i]);
12.             // 如果存在满足条件的二元组，再加上 nums[i] 就是结果三元组
13.             for (vector<int>& tuple : tuples) {
14.                 tuple.push采用back(nums[i]);
15.                 res.push采用back(tuple);
16.             }
17.             // 跳过第一个数字重复的情况，否则会出现重复结果
18.             while (i < n - 1 && nums[i] == nums[i + 1]) i++;
19.         }
20.         return res;
21.     }
22. ```

复制代码

admin1

1. ```C++
2. /* 注意：调用这个函数之前一定要先给 nums 排序 */
3.     vector<vector<int>> nSumTarget(
4.             vector<int>& nums, int n, int start, int target) {
6.         int sz = nums.size();
7.         vector<vector<int>> res;
8.         // 至少是 2Sum，且数组大小不应该小于 n
9.         if (n < 2 || sz < n) return res;
10.         // 2Sum 是 base case
11.         if (n == 2) {
12.             // 双指针那一套操作
13.             int lo = start, hi = sz - 1;
14.             while (lo < hi) {
15.                 int sum = nums[lo] + nums[hi];
16.                 int left = nums[lo], right = nums[hi];
17.                 if (sum < target) {
18.                     while (lo < hi && nums[lo] == left) lo++;
19.                 } else if (sum > target) {
20.                     while (lo < hi && nums[hi] == right) hi--;
21.                 } else {
22.                     res.push采用back({left, right});
23.                     while (lo < hi && nums[lo] == left) lo++;
24.                     while (lo < hi && nums[hi] == right) hi--;
25.                 }
26.             }
27.         } else {
28.             // n > 2 时，递归计算 (n-1)Sum 的结果
29.             for (int i = start; i < sz; i++) {
30.                 vector<vector<int>>
31.                         sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
32.                 for (vector<int>& arr : sub) {
33.                     // (n-1)Sum 加上 nums[i] 就是 nSum
34.                     arr.push采用back(nums[i]);
35.                     res.push采用back(arr);
36.                 }
37.                 while (i < sz - 1 && nums[i] == nums[i + 1]) i++;
38.             }
39.         }
40.         return res;
41.     }
42. ```

复制代码

admin

1. vector<vector<int>> nSumTarget(vector<int>& nums, int n, int start, int target){
2.         int sz = nums.size();
3.         vector<vector<int>> res;
4.         //至少是2Sum，且数组大小应该小于n
5.         if(n < 2 || sz < n) return res;
6.         //2Sum
7.         if(n == 2){
8.                 int l = start;
9.                 int r = nums.size() - 1;
10.             while(l < r){
11.                     int sum = nums[l] + nums[r];
12.                     int left = nums[l];
13.                     int right = nums[r];
14.                     if(sum == target){
15.                             res.push采用back({left, right});
16.                             //下面两行代码可以保证不出现重复的元素
17.                             while(l < r && nums[l] == left) l++;
18.                             while(l < r && nums[r] == right) r--;                       
19.                     }else if(sum > target){
20.                             //直接r--也可以，下面这行代码是对r--进行了优化
21.                             while(l < r && nums[r] == right) r--;       
22.                     }else if(sum < target){
23.                             while(l < r && nums[l] == left) l++;
24.                     }
25.             }
26.         }else{
27.                 //n > 2 递归的计算(n - 1)Sum
28.                 for(int i = start; i < sz; i++){
29.                         vector<vector<int>> sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
30.                         int num = sub.size();
31.                         for(int j = 0; j < num; j++){
32.                                 sub[j].push采用back(nums[i]);
33.                                 res.push采用back(sub[j]);
34.                         }
35.                         while(i < sz - 1 && nums[i] == nums[i + 1]) i++;
36.                 }
37.         }
38.         return res;       
39. }

复制代码

admin

1. class Solution {
2. public:
3.     vector<vector<int>> threeSum(vector<int>& nums) {
4.         return threeSumTarget(nums, 0);        
5.     }
7.     //返回3数之和为target的所有组合并且组合不能重复
8.     vector<vector<int>> threeSumTarget(vector<int>& nums, int target) {
9.         vector<vector<int>> res;
10.         sort(nums.begin(), nums.end());
11.         int size = nums.size();
12.         
13.         for(int i = 0; i < size; i++){
14.             vector<vector<int>> tuples = twoSumTarget(nums, i + 1, target - nums[i]);
15.             
16.             //如果存在满足条件的二元组，再加上nums[i]即为一个结果
17.             int n = tuples.size();
18.             for(int j = 0; j < n; j++){
19.                 tuples[j].push采用back(nums[i]);
20.                 res.push采用back(tuples[j]);
21.             }
22.             //跳过第一个数字重复的情况，否则会出现重复的结果
23.             while(i < size - 1 && nums[i] == nums[i + 1]){
24.                 i++;
25.             }
26.         }
27.         return res;
28.     }
30.     vector<vector<int>> twoSumTarget(vector<int>& nums, int start, int target){
31.             sort(nums.begin(), nums.end());
32.             vector<vector<int>> res;
33.             int l = start;
34.             int r = nums.size() - 1;
35.             while(l < r){
36.                     int sum = nums[l] + nums[r];
37.                     int left = nums[l];
38.                     int right = nums[r];
39.                     if(sum == target){
40.                             res.push采用back({left, right});
41.                             //下面两行代码可以保证不出现重复的元素
42.                             while(l < r && nums[l] == left) l++;
43.                             while(l < r && nums[r] == right) r--;                       
44.                     }else if(sum > target){
45.                             //直接r--也可以，下面这行代码是对r--进行了优化
46.                             while(l < r && nums[r] == right) r--;       
47.                     }else if(sum < target){
48.                             while(l < r && nums[l] == left) l++;
49.                     }
50.             }
51.             return res;
52.     }
54. };

复制代码

admin

1. vector<vector<int>> twoSumTarget(vector<int>& nums, int target){
2.         sort(nums.begin(), nums.end());
3.         vector<vector<int>> res;
4.         int l = 0;
5.         int r = nums.size() - 1;
6.         while(l < r){
7.                 int sum = nums[l] + nums[r];
8.                 int left = nums[l];
9.                 int right = nums[r];
10.                 if(sum == target){
11.                         res.push采用back({left, right});
12.                         //下面两行代码可以保证不出现重复的元素
13.                         while(l < r && nums[l] == left) l++;
14.                         while(l < r && nums[r] == right) r--;                       
15.                 }else if(sum > target){
16.                         //直接r--也可以，下面这行代码是对r--进行了优化
17.                         while(l < r && nums[r] == right) r--;       
18.                 }else if(sum < target){
19.                         while(l < r && nums[l] == left) l++;
20.                 }
21.         }
22.         return res;
23. }

复制代码

admin

1. typedef vector<vector<int>::iterator> Manager;
3. class Solution {
4. public:
5.   vector<vector<int>> nSum(vector<int> &nums, int target, int n) {
6.     if (nums.size() < n) return {}; // 特判，数组长度小于n时返回空
7.     sort(nums.begin(), nums.end()); // 数组排序
9.     Manager iters(n - 1, nums.begin()); // 指针数组
10.     vector<vector<int>> result; // 返回值
11.     vector<int> record; // 记录栈
12.     int cur采用n = n; // 当前所求的是几数之和
14.     // 当求完i数和（1. 遍历完；2. 从**it开始的i个数大于target）后，回溯到求i+1数和
15.     auto back = [&record, &target](Manager::iterator &it) {
16.       target += record.back();
17.       record.pop采用back();
18.       --it;
19.     };
21.     for (auto it = iters.begin();; ++*it) {
22.       cur采用n = n - record.size(); // 当前所求为cur采用n数之和
24.       // cur采用n数之和遍历完，回溯
25.       if (*it > nums.end() - cur采用n) {
26.         if (cur采用n == n) break;
27.         back(it);
28.         continue;
29.       }
31.       // 剪枝，排除不可能的情况
32.       if (accumulate(*it, *it + cur采用n, 0) > target) {
33.         if (cur采用n == n) break; // 直接返回结果
34.         back(it);
35.         continue;
36.       }
38.       // 求2数之和
39.       if (cur采用n == 2) {
40.         for (auto left = *it, right = nums.end() - 1; left < right;) {
41.           int sum = *left + *right;
42.           if (sum < target) {
43.             do { ++left; } while (left < right && *left == *(left - 1));
44.           } else if (sum > target) {
45.             do { --right; } while (left < right && *right == *(right + 1));
46.           } else {
47.             record.push采用back(*left);
48.             record.push采用back(*right);
49.             result.push采用back(record);
50.             record.pop采用back();
51.             record.pop采用back();
52.             do { ++left; } while (left < right && *left == *(left - 1));
53.             do { --right; } while (left < right && *right == *(right + 1));
54.           }
55.         }
56.         back(it);
57.         continue;
58.       }
60.       // 去重
61.       auto start = cur采用n == n ? *it == nums.begin() : *it == *(it - 1) + 1;
62.       if (!start && **it == *(*it - 1)) continue;
64.       // 优化，设当前求i数之和，从nums中从右往左选取i-1个数，计算i数之和，如果小于targe则右移it
65.       if (**it + accumulate(nums.end() - cur采用n + 1, nums.end(), 0) < target) continue;
67.       // 由求cur采用n数之和转换为求cur采用n - 1数之和
68.       record.push采用back(**it);
69.       target -= **it; // 记录当前选取的数
70.       ++it; // 右移it
71.       *it = *(it - 1); // 初始化下轮迭代的it
72.     }
73.     return result;
74.   }
75. };
77. https://leetcode.cn/problems/4sum/solutions/593183/nshu-zhi-he-by-zhiyuanlck-x98k/

复制代码

admin

1. class Solution {
2.     vector<vector<int>> nSum(vector<int>& nums, int target, int count) {
3.         if (nums.size() < count || count < 2)
4.             return {};
5.         sort(nums.begin(), nums.end());
6.         vector<vector<int>> result;
7.         vector<int> temp采用result(count, 0);
8.         vector<int> indices(count - 2, 0);          // 保存前 n - 2 个数的指针
9.         iota(indices.begin(), indices.end(), 0);    // 给前 n - 2 个指针初始化为 0, 1, 2, ..., n - 3
10.         while (true)
11.         {
12.             // 计算两数之和的目标值 (最终的目标值减去前 n - 2 个指针的值的和)
13.             long temp采用target = target;
14.             for (int i = 0; i < count - 2; i++)
15.                 temp采用target -= nums[indices[i]];
16.             
17.             // 求解两数之和问题
18.             int left = indices.back() + 1;
19.             int right = nums.size() - 1;
20.             while (left < right)
21.             {
22.                 if (nums[left] + nums[right] == temp采用target)
23.                 {
24.                     for (int i = 0; i < count - 2; i++)
25.                         temp采用result[i] = nums[indices[i]];
26.                     temp采用result[count - 2] = nums[left];
27.                     temp采用result[count - 1] = nums[right];
28.                     result.push采用back(temp采用result);
29.                     while (left < right && nums[left] == nums[left + 1])
30.                         left++;
31.                     while (left < right && nums[right] == nums[right - 1])
32.                         right--;
33.                     left++;
34.                     right--;
35.                 }
36.                 else
37.                 {
38.                     if (nums[left] + nums[right] > temp采用target)
39.                     {
40.                         right--;
41.                     }
42.                     else
43.                     {
44.                         left++;
45.                     }
46.                 }
47.             }
49.             // 更新前 n - 2 个指针
50.             for (int i = 0; i < count - 2; i++)
51.             {
52.                 int& cur = indices[count - 3 - i];
53.                 for (int origin = nums[cur]; cur < nums.size() - 2 - i && nums[cur] == origin; ++cur);
54.                 if (cur < nums.size() - 2 - i)
55.                 {
56.                     for (int j = 0; j < i; j++)
57.                     {
58.                         indices[count - 2 - i + j] = indices[count - 3 - i + j] + 1;
59.                     }
60.                     break;
61.                 }
62.             }
63.             if (count > 2 && indices.front() > nums.size() - count)
64.             {
65.                 break;
66.             }
67.         }
68.         return result;
69.     }
70. public:
71.     vector<vector<int>> fourSum(vector<int>& nums, int target) {
72.         //求解四数之和
73.         return nSum(nums, target, 4);
74.     }
75. };
78. 链接：https://leetcode.cn/problems/4sum/solutions/

复制代码

admin

1. class Solution {
2. public:
3.     vector<vector<int>> twoSum(vector<int>& nums, long target, int left){
4.         int right = nums.size() - 1;
5.         long sum2;
6.         vector<vector<int>> ans;
7.         while(left < right){
8.             sum2 = (long) nums[left] + nums[right];
9.             if(sum2 > target){
10.                 right--;
11.             }else if(sum2 < target){
12.                 left++;
13.             }else{
14.                 ans.push采用back({nums[left], nums[right]});
15.                 left++;
16.                 right--;
17.                 while(left < right && nums[right] == nums[right+1]){
18.                     right--;
19.                 }
20.                 while(left < right && nums[left] == nums[left-1]){
21.                     left++;
22.                 }
23.             }
24.         }
25.         return ans;
26.     }
27.     vector<vector<int>> nSum(vector<int>& nums, long target, int n, int left){
28.         vector<vector<int>> ans;
29.         vector<vector<int>> ans1;
30.         if(n == 2){
31.             ans = twoSum(nums, target, left);
32.         }else{
33.             for(int i=left; i<=nums.size() - n; i++){
34.                 if(i > left && nums[i] == nums[i-1]){
35.                     continue;
36.                 }
37.                 ans1 = nSum(nums, target - nums[i], n-1, i+1);
38.                 for(int j=0; j<ans1.size(); j++){
39.                     ans1[j].insert(ans1[j].begin(), nums[i]);
40.                 }
41.                 ans.insert(ans.end(), ans1.begin(), ans1.end());
42.             }  
43.         }
44.         return ans;
45.     }
46.     vector<vector<int>> fourSum(vector<int>& nums, int target) {
47.         vector<vector<int>> ans;
48.         sort(nums.begin(), nums.end());
49.         int n = nums.size();
50.         if(n < 4){
51.             return ans;
52.         }
53.         ans = nSum(nums, (long)target, 4, 0);
54.         return ans;
55.     }
56. };
59. 链接：https://leetcode.cn/problems/4sum/solutions/2090909/tong-guo-di-gui-ke-yi-qiu-nge-shu-zi-zhi-rc3a/
60. 。

复制代码

jxmjg

1. class Solution {
2. private:
3.     vector<vector<int>> p;
4.     vector<int> v={1,2,3,4,5,6,7,8,9};
5. public:
6.     void helper(vector<int> &vec,int l,int k,int n,int index) {
7.         if(k==0 && n==0) {
8.             p.push采用back(vec);
9.             return;
10.         } else if(k==0) return;
11.         else if(n<0) return;
12.         
13.         for(int i=l;i<v.size();i++) {
14.             vec[index]=v[i];
15.             helper(vec,i+1,k-1,n-vec[index],index+1);
16.         }
17.         return;
18.     }
19.     vector<vector<int>> combinationSum3(int k, int n) {
20.         vector<int> vec(k,0);
21.         helper(vec,0,k,n,0);
22.         return p;
23.     }
24. };

复制代码