พิมพ์ Subarrays ทั้งหมดที่มีผลรวมเป็น 0 ใน C++

ในปัญหานี้ เราจะได้รับ array ของจำนวนเต็ม และต้องพิมพ์ subarrays ทั้งหมดจาก array นี้ที่มีผลรวมเท่ากับ 0

ตัวอย่างเพื่อความเข้าใจ

Input: array = [-5, 0, 2, 3, -3, 4, -1]
Output: Subarray with sum 0 is from 1 to 4.
Subarray with sum 0 is from 5 to 7
Subarray with sum 0 is from 0 to 7

เพื่อแก้ปัญหานี้ เราจะตรวจสอบ subarrays ทั้งหมดที่เป็นไปได้ และตรวจสอบว่าผลรวมของ subarrays เหล่านั้นเท่ากับ 0 หรือไม่ และพิมพ์ออกมา วิธีนี้เข้าใจง่ายแต่ซับซ้อน และ time complexity เป็น O(n²)

วิธีที่ดีกว่าคือใช้ Hashing สำหรับการแก้ปัญหานี้ เราจะหาผลรวม ถ้าเท่ากับ 0 ให้เพิ่มลง Hash table

อัลกอริทึม

ขั้นตอนที่ 1: สร้างตัวแปร sum
ขั้นตอนที่ 2: ถ้า sum = 0 subarray เริ่มจาก index 0 ถึง end index ของ array
ขั้นตอนที่ 3: ถ้า current sum อยู่ใน hash table
ขั้นตอนที่ 4: ถ้า sum มีอยู่แล้ว subarray จาก i+1 ถึง n ต้องเป็นศูนย์
ขั้นตอนที่ 5: มิฉะนั้น ให้ insert ลง hash table

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

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

vector< pair<int, int> > findSubArrayWithSumZero(int arr[], int n) {
    unordered_map<int, vector<int> > map;
    vector <pair<int, int>> out;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
        if (sum == 0)
            out.push_back(make_pair(0, i));
        if (map.find(sum) != map.end()) {
            vector<int> vc = map[sum];
            for (auto it = vc.begin(); it != vc.end(); it++)
                out.push_back(make_pair(*it + 1, i));
        }
        map[sum].push_back(i);
    }
    return out;
}

int main() {
    int arr[] = {-5, 0, 2, 3, -3, 4, -1};
    int n = sizeof(arr) / sizeof(arr[0]);
    vector<pair<int, int> > out = findSubArrayWithSumZero(arr, n);
    if (out.size() == 0)
        cout << "No subarray exists";
    else
        for (auto it = out.begin(); it != out.end(); it++)
            cout << "Subarray with sum 0 is from " << it->first << " to " << it->second << endl;
    return 0;
}

ผลลัพธ์

Subarray with sum 0 is from 1 to 1
Subarray with sum 0 is from 0 to 3
Subarray with sum 0 is from 3 to 4
Subarray with sum 0 is from 0 to 6
Subarray with sum 0 is from 4 to 6