4C++での合計

これを解決するには、次の手順に従います-

• 実際の合計は、kSum（）と呼ばれる関数を使用して実行されます。これには、配列、開始、k、およびターゲットが含まれます。最初に関数はk値4で呼び出されます。関数は次のようになります
• 配列解像度を定義する
• k =2の場合、
  • 左：=開始と右：=配列サイズ– 1
  • サイズ2の別のアレイ温度を定義します
  • 左<右
    • arr [left] + arr [right] =targetの場合、
      • temp [0]：=arr [left]、temp [1]：=arr [right]、およびtempをresに挿入
      • 左<右およびarr[左]=arr[左+1]
        • lを1増やします
      • 左<右およびarr[右]=arr [右– 1]
        • rを1減らします
      • lを1増やし、rを1減らします
    • それ以外の場合、arr [left] + arr [right]>ターゲットの場合、右に1減少します
    • それ以外の場合は、左に1つ増やします
• その他
  • 範囲内のiの場合、サイズ– k、
    • i>が開始してarr[i]=arr [i-1]の場合、次の手順をスキップして続行します
    • 1つの2次元配列tempを定義します：=kSum（arr、i + 1、k – 1、target – arr [i]）
    • 0からtempの範囲のjの場合
      • temp [j]
      の後にarr[i]を挿入します
    • tempのすべての要素をresにコピーします
• return 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]]