C++ 中的四数之和

假设我们有一个数字数组。它存储 n 个整数，数组中有四个元素 a、b、c 和 d。我们还有一个目标值，使得 a + b + c + d = 目标值。找到数组中所有满足此条件的唯一四元组。因此，如果数组是 [-1,0,1,2,0,-2] 且目标值为 0，则结果将是 [[-1, 0, 0, 1],[-2, -1, 1, 2], [-2, 0, 0, 2]]

为了解决这个问题，我们将遵循以下步骤：

  • 实际的求和是使用名为 kSum() 的函数完成的。该函数接受数组、起始位置、k 和目标值作为参数。最初，函数将以 k 值 4 调用。函数如下所示：
  • 定义一个数组 res
  • 如果 k = 2，则
    • left := start right := 数组大小 – 1
    • 定义另一个大小为 2 的数组 temp
    • 当 left < right 时
      • 如果 arr[left] + arr[right] = target，则
        • temp[0] := arr[left]，temp[1] := arr[right]，并将 temp 插入 res
        • 当 left < right 且 arr[left] = arr[left + 1] 时
          • 将 l 增加 1
        • 当 left < right 且 arr[right] = arr[right – 1] 时
          • 将 r 减小 1
        • 将 l 增加 1 并将 r 减小 1
      • 否则，如果 arr[left] + arr[right] > target，则将 right 减小 1
      • 否则，将 left 增加 1
  • 否则
    • 对于 i 的范围从 start 到数组大小 – k
      • 如果 i > start 且 arr[i] = arr[i - 1]，则跳过下一步并继续
      • 定义一个二维数组 temp := kSum(arr, i + 1, k – 1, target – arr[i])
      • 对于 j 的范围从 0 到 temp
        • 在 temp[j] 之后插入 arr[i]
      • 将 temp 的所有元素复制到 res
  • 返回 res

示例（C++）

让我们看看下面的实现，以便更好地理解：

 在线演示

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<int> > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   void addAll(vector < vector <int> >& res, vector < vector <int> >& temp){
      for(int i = 0; i < temp.size(); i++)res.push_back(temp[i]);
   }
   vector<vector<int>> fourSum(vector<int>& nums, int target) {
      sort(nums.begin(), nums.end());
      return kSum(nums, 0, 4, target);
   }
   vector < vector <int> > kSum(vector <int>& arr, int start, int k, int target){
      vector < vector <int> > res;
      if(k == 2){
         int left = start;
         int right = arr.size() - 1;
         vector <int> temp(2);
         while(left < right){
            if(arr[left] + arr[right] == target){
               temp[0] = arr[left];
               temp[1] = arr[right];
               res.push_back(temp);
               while(left < right && arr[left] == arr[left + 1])left++;
               while(left < right && arr[right] == arr[right - 1])right--;
               left++;
               right--;
            }
            else if(arr[left] + arr[right] > target)right--;
            else left ++;
         }
      }
      else{
         for(int i = start; i < (int)arr.size() - k + 1; i++){
            if(i > start && arr[i] == arr[i - 1])continue;
            vector < vector <int> > temp = kSum(arr, i + 1, k - 1, target - arr[i]);
            for(int j = 0; j < temp.size(); j++){
               temp[j].push_back(arr[i]);
            }
            addAll(res, temp);
         }
      }
      return res;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,0,-1,0,-2,2};
   print_vector(ob.fourSum(v, 0));
}

输入

[1,0,-1,0,-2,2]
0

输出

[[1,2,-1,-2],[0,2,0,-2],[0,1,0,-1]]

更新于：2020年4月27日

475 次浏览

启动您的职业生涯

通过完成课程获得认证

开始学习
广告