C++에서 합이 같은 배열 분할

<시간/>

n개의 정수가 있는 배열이 있다고 가정하고 다음 조건을 따르는 삼중항(i, j, k)이 있는지 찾아야 합니다. -

0
부분배열의 합(0, i - 1), (i + 1, j - 1), (j + 1, k - 1) 및 (k + 1, n - 1)은 동일합니다.

하위 배열(L, R)은 인덱스가 L인 요소에서 시작하여 인덱스가 R인 요소까지 원래 배열의 조각입니다.

따라서 입력이 [1,2,1,2,1,2,1]과 같으면 출력은 i =1, j =3, k =5와 같이 True가 됩니다.

sum(0, i - 1) = 1 sum(0, 0) = 1
sum(i + 1, j - 1) = 1 sum(2, 2) = 1
sum(j + 1, k - 1) = 1 sum(4, 4) = 1
sum(k + 1, n - 1) = 1 sum(6, 6) = 1

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

n :=숫자 크기
크기가 n인 배열 합계 정의
합계[0] :=숫자[0]
initialize i :=1의 경우, i
- 합계[i] :=합계[i] + (숫자[i] + 합계[i - 1])
j 초기화:=3의 경우 j − n일 때 업데이트(j를 1만큼 증가), −
- 한 세트 정의
- initialize i :=1의 경우 i
  - sum1 :=합계[i - 1]
  - 합계2 :=합계[j - 1] - 합계[i]
  - sum1이 sum2와 같으면 -
    - sum1을 s
      에 삽입
- k:=j + 2 초기화의 경우 k
  - sum1 :=합계[k - 1] - 합계[j]
  - sum2 :=합계[n - 1] - 합계[k]
  - sum1이 sum2와 같고 sum1이 s에 있으면 -
    - true를 반환
거짓 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool splitArray(vector<int>& nums) {
      int n = nums.size();
      vector<int> sums(n);
      sums[0] = nums[0];
      for (int i = 1; i < n; i++) {
         sums[i] += (nums[i] + sums[i - 1]);
      }
      for (int j = 3; j < n; j++) {
         set<int> s;
         for (int i = 1; i < j - 1; i++) {
            int sum1 = sums[i - 1];
            int sum2 = sums[j - 1] - sums[i];
            if (sum1 == sum2)
               s.insert(sum1);
         }
         for (int k = j + 2; k < n - 1; k++) {
            int sum1 = sums[k - 1] - sums[j];
            int sum2 = sums[n - 1] - sums[k];
            if (sum1 == sum2 && s.count(sum1))
               return true;
            }
         }
         return false;
      }
};
main(){
   Solution ob;
   vector<int> v = {1,2,1,2,1,2,1};
   cout << (ob.splitArray(v));
}

입력

{1,2,1,2,1,2,1}