Chia mảng với tổng bằng trong C ++

Giả sử chúng ta có một mảng với n số nguyên, chúng ta phải tìm xem có các bộ ba (i, j, k) tuân theo các điều kiện này không -

0
Tổng của các mảng con (0, i - 1), (i + 1, j - 1), (j + 1, k - 1) và (k + 1, n - 1) sẽ bằng nhau.

Mảng con (L, R) là một phần của mảng ban đầu bắt đầu từ phần tử được lập chỉ mục L đến phần tử được lập chỉ mục R.

Vì vậy, nếu đầu vào là [1,2,1,2,1,2,1], thì đầu ra sẽ là Đúng, như i =1, j =3, k =5.

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

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

n:=kích thước của nums
Xác định tổng mảng có kích thước n
tổng [0]:=nums [0]
để khởi tạo i:=1, khi i
- tổng [i]:=sums [i] + (nums [i] + sums [i - 1])
để khởi tạo j:=3, khi j - n, cập nhật (tăng j lên 1), do -
- Xác định một bộ s
- để khởi tạo i:=1, khi i
  - sum1:=sums [i - 1]
  - sum2:=sums [j - 1] - sums [i]
  - nếu sum1 giống sum2, thì -
    - chèn sum1 vào s
- để khởi tạo k:=j + 2, khi k
  - sum1:=sums [k - 1] - sums [j]
  - sum2:=sums [n - 1] - sums [k]
  - nếu sum1 giống sum2 và sum1 bằng s thì -
    - trả về true
trả về false

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

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

Chia mảng với tổng bằng trong C ++

Ví dụ

Đầu vào

Đầu ra