Kiểm tra tồn tại mảng con tổng bằng 0 trong C++

Cho mảng arr[] kích thước n. Nhiệm vụ: kiểm tra có mảng con nào tổng bằng 0 không.

Ví dụ:

Đầu vào: arr[] = {3, 1, -2, 1, 4, 5}

Đầu ra: Yes

Giải thích: Mảng con {1, -2, 1} tổng = 0.

Phương pháp giải

Cách đơn giản: kiểm tra tất cả mảng con O(n^2).

Cách tối ưu: dùng hashing. Duyệt mảng, tính tổng tiền tố (prefix sum). Nếu tổng tiền tố bằng 0 hoặc đã xuất hiện trước đó => tồn tại mảng con tổng 0. O(n) thời gian, O(n) không gian.

Chương trình minh họa

Ví dụ

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

bool isSubArraySumZero(int arr[], int n) {
    unordered_set<int> sumHash;
    int currSum = 0;
    for (int i = 0; i < n; i++) {
        currSum += arr[i];
        if (currSum == 0 || sumHash.find(currSum) != sumHash.end())
            return true;
        sumHash.insert(currSum);
    }
    return false;
}

int main() {
    int arr[] = { 3, 1, -2, 1, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    if (isSubArraySumZero(arr, n))
        cout << "SubArray with sum equal to 0 exists in the array";
    else
        cout << "No subarray exists";
    return 0;
}

Kết quả

SubArray with sum equal to 0 exists in the array