หาผลรวมของ Subarray Sum ที่ไม่ซ้ำกันในอาร์เรย์ด้วย C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ที่ประกอบด้วย n จำนวนเต็ม งานของเราคือ การหาผลรวมของ subarray sum ที่ไม่ซ้ำกันทั้งหมด โดย subarray sum คือผลรวมของสมาชิกใน subarray นั้น

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

Input : arr[] = {1, 2, 4} 
Output : 23

คำอธิบาย

Subarray ทั้งหมด: (1), (2), (4), (1,2), (2,4), (1,2,4)
ผลรวม = 1 + 2 + 4 + (1+2) + (2+4) + (1+2+4) = 23

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

วิธีแก้หนึ่งคือการเก็บ subarray sum ทั้งหมด แล้วจัดเรียงเพื่อหาค่าที่ไม่ซ้ำกัน จากนั้นรวมเฉพาะค่าที่ไม่ซ้ำนั้นๆ

อัลกอริทึม

• ขั้นตอนที่ 1 − หาผลรวมของทุก subarray และเก็บไว้ในเวกเตอร์
• ขั้นตอนที่ 2 − จัดเรียงเวกเตอร์
• ขั้นตอนที่ 3 − ตรวจสอบค่าที่ไม่ซ้ำกัน ตั้งค่าที่ซ้ำให้เป็น 0
• ขั้นตอนที่ 4 − คำนวณและแสดงผลรวม

ตัวอย่างโค้ด (วิธีที่ 1: ใช้การจัดเรียง)

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

long int findSumOfSubArraySum(int arr[], int n) {
    int i, j;
    long int sumArrayTill[n + 1] = { 0 };
    for (i = 0; i < n; i++)
        sumArrayTill[i + 1] = sumArrayTill[i] + arr[i];
    
    vector<long int> subArraySum;
    for (i = 1; i <= n; i++)
        for (j = i; j <= n; j++)
            subArraySum.push_back(sumArrayTill[j] - sumArrayTill[i - 1]);
    
    sort(subArraySum.begin(), subArraySum.end());
    
    for (i = 0; i < subArraySum.size() - 1; i++) {
        if (subArraySum[i] == subArraySum[i + 1]) {
            j = i + 1;
            while (subArraySum[j] == subArraySum[i] && j < subArraySum.size()) {
                subArraySum[j] = 0;
                j++;
            }
            subArraySum[i] = 0;
        }
    }
    
    long sum = 0;
    for (i = 0; i < subArraySum.size(); i++)
        sum += subArraySum[i];
    return sum;
}

int main() {
    int arr[] = { 1, 2, 4, 7, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The sum of all unique subarray sum is " << findSumOfSubArraySum(arr, n);
    return 0;
}

ผลลัพธ์

The sum of all unique subarray sum is 144

วิธีที่ 2: ใช้ Hash Table (มีประสิทธิภาพมากกว่า)

อีกวิธีหนึ่งคือการใช้ Hash Table เราจะหา subarray sums และเก็บไว้ใน hash table พร้อมนับจำนวนครั้งที่ปรากฏ จากนั้นหาผลรวมของ subarray ที่มี hash count เท่ากับ 1 (คือไม่ซ้ำกัน)

ตัวอย่างโค้ด (วิธีที่ 2)

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

long int findSumOfSubArraySum(int arr[], int n) {
    int sumSubArraySum = 0;
    unordered_map<int, int> sumSubArray;
    
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {
            sum += arr[j];
            sumSubArray[sum]++;
        }
    }
    
    for (auto itr : sumSubArray)
        if (itr.second == 1)
            sumSubArraySum += itr.first;
    
    return sumSubArraySum;
}

int main() {
    int arr[] = { 1, 2, 4, 7, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The sum of all unique subarray sum is " << findSumOfSubArraySum(arr, n);
    return 0;
}

ผลลัพธ์

The sum of all unique subarray sum is 124