多数之和问题（nSum）

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.   

复制代码

admin

1. class Solution {
2. public:
3.     vector<vector<int>> result;
4.     vector<vector<int>> fourSum(vector<int>& nums, int target) {
5.         sort(nums.begin(),nums.end());
6.         vector<int> leaf;
7.         int n = 4;
8.         if(nums.size()==n){//剪枝
9.             long long temp=0;
10.             for(int i=0;i<n;i++){
11.                 temp+=nums[i];
12.             }
13.             if(temp==target)
14.                 result.push采用back(nums);
15.             return result;
16.         }
17.         
18.         nSum(nums,0,target,n,leaf);
19.         return result;
20.     }
21.     void nSum(const vector<int>& nums,int index,long long target,int n,vector<int>& leaf){
22.         if(n==2){
23.             int left=index,right=nums.size()-1;
24.             while(left<right){
25.                 if(nums[left]+nums[right]<target){
26.                     left++;
27.                     while(left<right&&nums[left-1]==nums[left])//去重
28.                         left++;
29.                 }
30.                 else if(nums[left]+nums[right]>target){
31.                     right--;
32.                     while(left<right&&nums[right+1]==nums[right])
33.                         right--;
34.                 }
35.                 else{
36.                     leaf.push采用back(nums[left]);
37.                     leaf.push采用back(nums[right]);
38.                     result.push采用back(leaf);
39.                     leaf.pop采用back();
40.                     leaf.pop采用back();
41.                     //继续寻找
42.                     left++;
43.                     while(left<right&&nums[left-1]==nums[left])
44.                         left++;
45.                 }
46.             }
47.             return;
48.         }
49.         if(n>2&&nums.size()-index>=n) {      
50.             for(int i=index;i<nums.size()-n+1;i++){
51.                 //去重
52.                 if(i>index&&nums[i]==nums[i-1])
53.                     continue;
54.                 //-----超限剪枝
55.                 long long temp = nums[i],temp2=nums[i];   
56.                 for(int j=1;j<n;j++){
57.                     temp+=nums[i+j];
58.                     temp2+=nums[nums.size()-j];
59.                 }
60.                 if(temp>target||temp2<target)
61.                     continue;
62.                 //----------
64.                 leaf.push采用back(nums[i]);
65.                 nSum(nums, i+1, target-nums[i],n-1, leaf);
66.                 leaf.pop采用back();
67.             }
68.         }  
69.     }
70. };

复制代码

admin

1. class Solution {
2. public:
3.     // 调用这个函数之前需要先对nums排序
4.     vector<vector<int>> nSum(vector<int>& nums, int n, int start, long long target) {
5.         if(n == 2) {
6.             // 两数之和
7.             int i = start, j = nums.size()-1;
8.             vector<vector<int>> ret;
9.             while(i < j) {
10.                 int left = nums[i], right = nums[j], sum = nums[i]+nums[j];
11.                 if(sum > target) {
12.                     while(i < j && nums[j] == right) --j;
13.                 } else if(sum < target) {
14.                     while(i < j && nums[i] == left) ++i;
15.                 } else {
16.                     ret.push采用back({left, right});
17.                     while(i < j && nums[i] == left) ++i;
18.                     while(i < j && nums[j] == right) --j;
19.                 }
20.             }
21.             return ret;
22.         } else {
23.             vector<vector<int>> ret;
24.             for(int i = start; i < nums.size()-n+1;) {
25.                 int num = nums[i];
26.                 // 剪枝
27.                 if ((num > 0 && target < 0) || (target > 0 && nums[nums.size()-1] < 0)) {
28.                     // 不可能成立
29.                     break;
30.                 }
31.                 vector<vector<int>> suffix = nSum(nums, n-1, i+1, (long long)target-num);
32.                 for(auto vec : suffix) {
33.                     vec.push采用back(num);
34.                     ret.push采用back(vec);
35.                 }
36.                 // 去重
37.                 while(i < nums.size()-n+1 && nums[i] == num) ++i;
38.             }
39.             return ret;
40.         }
42.     }
43.     vector<vector<int>> fourSum(vector<int>& nums, int target) {
44.         if(nums.size() < 4) {
45.             return {};
46.         }
47.         sort(nums.begin(), nums.end());
48.         return nSum(nums, 4, 0, target);
49.     }
50. };

复制代码