多数之和问题（nSum）

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. };

复制代码

nkmjg

2. static        vector<vector<int>> nSumHelper(const vector<int> &nums, vector<int> &before, int n, int target) {
3.                 vector<vector<int>> res;
4.                 if (n <= 0) {
5.                         return res;
6.                 }
7.                 if (n == 1) {
8.                         for (auto value : nums) {
9.                                 if (value == target) {
11.                                         //res.push采用back({value});
12.                                         vector<int> temp;
13.                                         temp.push采用back(value);
14.                                         res.push采用back(temp);
15.                                 }
16.                         }
17.                         return res;
18.                 }
19.                 if (n == 2) {
20.                         int i = -1;
21.                         if (!before.empty()) {
22.                                 i = before.back();
23.                         }
24.                         int left = i + 1;
25.                         int right = (int)nums.size() - 1;
26.                         while (left < right) {
27.                                 vector<int> temp = before;
28.                                 int sum = nums[left] + nums[right];
29.                                 if (sum == target) {
30.                                         temp.push采用back(left);
31.                                         temp.push采用back(right);
32.                                         vector<int> t;
33.                                         for (auto index : temp) {
34.                                                 t.push采用back(nums[index]);
35.                                         }
36.                                         res.push采用back(move(t));
37.                                         ++left;
38.                                         --right;
39.                                         while (left < right && nums[left] == nums[left - 1]) {
40.                                                 ++left;
41.                                         }
42.                                         while (left < right && nums[right] == nums[right + 1]) {
43.                                                 --right;
44.                                         }
45.                                         continue;
46.                                 } else if (sum < target) {
47.                                         ++left;
48.                                 } else {
49.                                         --right;
50.                                 }
51.                         }
52.                         return res;
53.                 }
54.                 int i = -1;
55.                 if (!before.empty()) {
56.                         i = before.back();
57.                 }
58.                 for (int j = i + 1; j < nums.size(); ++j) {
59.                         if (j > i + 1 && nums[j] == nums[j - 1]) {
60.                                 continue;
61.                         }
62.                         before.push采用back(j);
63.                         auto r1 = nSumHelper(nums, before, n - 1, target - nums[j]);
64.                         if (!r1.empty()) {
65.                                 for (auto &v : r1) {
66.                                         res.push采用back(v);
67.                                 }
68.                         }
69.                         before.pop采用back();
70.                 }
71.                 return res;
72.         }
74. static        vector<vector<int>> nSum(vector<int> &nums, int n, int target) {
75.                 vector<vector<int>> ans;
76.                 if (nums.size() < n) {
77.                         return ans;
78.                 }
79.                 sort(nums.begin(), nums.end());
80.                 vector<int> before;
81.                 return nSumHelper(nums, before, n, target);
82.         }
83.         ///    ===============提交的业务代码=============================
84.         class Solution {
85.         public:
86.                 vector<vector<int>> fourSum(vector<int>& nums, int target) {
87.                         return nSum(nums, 4, target);
88.                 }
89.         };

复制代码

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. };

复制代码

admin

递归思想做n数和

1. class Solution {
2. public:
3. vector<vector> fourSum(vector& nums, int target) {
4. int size = nums.size();
5. int number = 4;
6. if(size < 4){
7. return {};
8. }
9. sort(nums.begin(), nums.end());
10. if((nums[0] > 0 && target < 0) || (nums[nums.size()-1] < 0 && target > 0)){
11. return {};
12. }
13. getRes(nums, number, target,0);
14. return result;
15. }
16. void getRes(vector& nums, int number, long target, int i){
17. if(number > 2){
18. for(int j = i;j < nums.size();j++){
19. while(j > i && j<nums.size() && nums[j] == nums[j-1]){
20. j++;
21. }
22. if(j < nums.size()){
23. temp.push采用back(nums[j]);
24. getRes(nums, number-1,target - nums[j],j+1);
25. temp.pop采用back();
26. }
27. }
28. }else{
29. int left = i;
30. int right = nums.size()-1;
31. while(left < right){
32. int twoNum = nums[left] + nums[right];
33. if(twoNum > target){
34. right--;
35. } else if(twoNum < target){
36. left++;
37. } else {
38. temp.push采用back(nums[left]);
39. temp.push采用back(nums[right]);
40. result.push采用back(temp);
41. temp.pop采用back();
42. temp.pop采用back();
43. left++;
44. right--;
45. while(left<right && nums[left] == nums[left-1]){
46. left++;
47. }
48. while(left < right && nums[right] == nums[right+1]){
49. right--;
50. }
51. }
52. }
53. }
54. }
55. private:
56. vector temp;
57. vector<vector> result;
58. };
60.   

复制代码