多数之和问题（nSum）

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

复制代码