设为首页收藏本站
切换到窄版

 找回密码
 立即注册

QQ登录

只需一步，快速开始

搜索
热搜: 活动 交友 discuz
中国膜结构网»论坛 › 二次开发 › ObjectARX | VC++ › 多数之和问题（nSum）
12下一页
返回列表 发新帖
查看: 486|回复: 14

多数之和问题（nSum）

[复制链接]
admin

1

主题

0

回帖

43

积分

管理员

积分
43
发表于 2024-3-7 21:06:03 | 显示全部楼层
  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

主题

0

回帖

43

积分

管理员

积分
43
发表于 2024-3-7 21:06:15 | 显示全部楼层
  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

主题

0

回帖

43

积分

管理员

积分
43
发表于 2024-3-7 21:06:24 | 显示全部楼层
  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

主题

0

回帖

43

积分

管理员

积分
43
发表于 2024-3-8 17:26:22 | 显示全部楼层
  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

主题

0

回帖

43

积分

管理员

积分
43
发表于 2024-3-8 17:30:51 | 显示全部楼层
  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

主题

0

回帖

43

积分

管理员

积分
43
发表于 2024-3-8 17:35:03 | 显示全部楼层
  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

主题

0

回帖

0

积分

管理员

积分
0
发表于 2024-3-11 18:31:53 | 显示全部楼层
  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

主题

0

回帖

0

积分

管理员

积分
0
发表于 2024-3-13 07:58:09 | 显示全部楼层
  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

主题

0

回帖

43

积分

管理员

积分
43
发表于 2024-3-16 18:29:17 | 显示全部楼层
  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

1

主题

0

回帖

43

积分

管理员

积分
43
发表于 2024-3-16 18:57:19 | 显示全部楼层
递归思想做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.   
复制代码
回复

举报

下一页 »
12下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|膜结构网

GMT+8, 2025-1-10 16:43 , Processed in 0.085990 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表