ตรวจสอบว่ามีซับอาร์เรย์ผลรวมเป็น 0 ใน C++

โจทย์

ได้รับอาร์เรย์ arr[] ทางเราต้อง ตรวจสอบว่ามีซับอาร์เรย์ (Subarray) ที่ผลรวมเป็น 0 หรือไม่

ตัวอย่าง

Input: arr[] = {3, 1, -2, 1, 4, 5}

Output: Yes

อธิบาย: ซับอาร์เรย์ {1, -2, 1} ผลรวม = 0

แนวทางแก้ปัญหา

ใช้ Hashing (Prefix Sum):

1. คำนวณ Prefix Sum ขณะท่องอาร์เรย์
2. ถ้า Prefix Sum ซ้ำ (หรือเป็น 0) -> มีซับอาร์เรย์ผลรวม 0
3. เก็บ Prefix Sum ใน Hash Set

โปรแกรมตัวอย่าง

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

ผลลัพธ์

SubArray with sum equal to 0 exists in the array