Tách mảng với tổng bằng nhau trong C++

Giới thiệu

Cho mảng nums độ dài n. Tìm 3 chỉ số i, j, k thỏa mãn:

• 0 < i, i+1 < j, j+1 < k < n-1
• 4 đoạn con có tổng bằng nhau: [0, i-1], [i+1, j-1], [j+1, k-1], [k+1, n-1].

Thuật toán: Prefix Sum + Hash Set

1. Tính mảng prefix sum sums.
2. Duyệt j từ 3 đến n-2 (vị trí ngăn cách giữa đoạn 2 và 3).
3. Với mỗi j, duyệt từ 1 đến j-2, tính sum1 = sums[i-1], sum2 = sums[j-1] - sums[i]. Nếu bằng nhau, lưu vào set valid.
4. Duyệt k từ j+2 đến n-2, tính sum3 = sums[k-1] - sums[j], sum4 = sums[n-1] - sums[k]. Nếu sum3 == sum4 và sum3 trong valid → tìm thấy.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool splitArray(vector& nums) {
        int n = nums.size();
        vector sums(n);
        sums[0] = nums[0];
        for (int i = 1; i < n; i++) sums[i] = sums[i-1] + nums[i];
        for (int j = 3; j < n; j++) {
            unordered_set valid;
            for (int i = 1; i < j-1; i++) {
                int sum1 = sums[i-1];
                int sum2 = sums[j-1] - sums[i];
                if (sum1 == sum2) valid.insert(sum1);
            }
            for (int k = j+2; k < n-1; k++) {
                int sum3 = sums[k-1] - sums[j];
                int sum4 = sums[n-1] - sums[k];
                if (sum3 == sum4 && valid.count(sum3)) return true;
            }
        }
        return false;
    }
};

int main() {
    Solution ob;
    vector v = {1,2,1,2,1,2,1};
    cout << ob.splitArray(v); // Output: 1 (true), i=1,j=3,k=5
    return 0;
}

Phân tích

• Thời gian: O(n²) – lồng j, i, k.
• Không gian: O(n) – prefix sum + set.

LeetCode 548 "Split Array with Equal Sum".