4C++의 합

숫자 배열이 있다고 가정합니다. n개의 정수를 저장하고 배열에 4개의 요소 a, b, c 및 d가 있습니다. + b + c + d =target과 같은 또 다른 목표 값이 있습니다. 상황을 만족하는 배열에서 모든 고유한 사중항을 찾습니다. 따라서 배열이 [-1,0,1,2,0,-2]이고 대상이 0이면 결과는 [[-1, 0, 0, 1],[-2, -1, 1, 2], [-2, 0, 0, 2]]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 실제 합계는 kSum()이라는 함수를 사용하여 수행됩니다. 이것은 배열, 시작, k 및 대상을 사용합니다. 초기에 함수는 k 값 4로 호출됩니다. 함수는 다음과 같습니다.
• 배열 해상도 정의
• k =2이면
  • 왼쪽 :=시작 및 오른쪽 :=배열 크기 – 1
  • 크기 2의 다른 어레이 온도 정의
  • 왼쪽 <오른쪽
    • arr[left] + arr[right] =target이면
      • temp[0] :=arr[left], temp[1] :=arr[right], res에 temp 삽입
      • left
      • l을 1씩 증가
    • left 동안
    • r 1 감소
  • l을 1 증가시키고 r을 1 감소
• arr[left] + arr[right]> target이면 오른쪽으로 1 감소
• 그렇지 않으면 왼쪽으로 1 증가

예시(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]]