หา Subarray ที่มีผลรวมเท่ากับค่าที่กำหนด (รองรับตัวเลขลบ) ใน C++

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

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

Input : arr[] = {2, 5, -1, 4, 6, -9, 5} sum = 14 
Output : subarray = {5, -1, 4, 6}

คำอธิบาย

Subarray sum = 5 - 1 + 4 + 6 = 14

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

วิธีแก้ที่ง่ายคือการใช้ Nested Loop เราจะวนลูปผ่านอาร์เรย์ และใช้ลูปภายในเพื่อหา subarray สำหรับแต่ละ subarray เราจะหาผลรวมของสมาชิกทั้งหมดและเปรียบเทียบกับค่าที่กำหนด หากเท่ากัน ให้พิมพ์ subarray นั้นออกมา

อัลกอริทึม (วิธีง่าย)

• ขั้นตอนที่ 1 − วนลูปผ่านอาร์เรย์, i → 0 ถึง (n-1)
  • ขั้นตอนที่ 1.1 − สำหรับแต่ละสมาชิก หาผลรวมของทุก subarray ที่เป็นไปได้
  • ขั้นตอนที่ 1.2 − หากผลรวมของ subarray ปัจจุบันเท่ากับค่าที่กำหนด ให้พิมพ์ subarray นั้น
• ขั้นตอนที่ 2 − หากเดินครบทุกสมาชิกแล้วไม่พบ subarray ให้พิมพ์ "No subarray with the given sum found!"

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

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

void printSubArray(int arr[], int i, int j) {
    cout << "{ ";
    for (; i < j; i++)
        cout << arr[i] << " ";
    cout << "}";
}

int findSubArrayWithSum(int arr[], int n, int sum) {
    int currSum;
    for (int i = 0; i < n; i++) {
        currSum = arr[i];
        for (int j = i + 1; j <= n; j++) {
            if (currSum == sum) {
                cout << "Subarray with given sum : ";
                printSubArray(arr, i, j);
                return 1;
            }
            if (currSum > sum || j == n)
                break;
            currSum = currSum + arr[j];
        }
    }
    cout << "No subarray found";
    return 0;
}

int main() {
    int arr[] = { 2, 5, -1, 4, 6, -9, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = 14;
    findSubArrayWithSum(arr, n, sum);
    return 0;
}

ผลลัพธ์

Subarray with given sum : { 5 -1 4 6 }

วิธีที่ดีกว่า: ใช้ Hash Map (Prefix Sum)

วิธีที่มีประสิทธิภาพมากกว่าคือการใช้ Hash Map เพื่อเก็บ Prefix Sum จนถึงดัชนีปัจจุบัน สำหรับดัชนีใดๆ เราตรวจสอบว่ามี subarray ที่ให้ผลรวมเท่ากับค่าที่ต้องการหรือไม่ โดยตรวจสอบว่ามี prefix sum ที่มีค่าเท่ากับ (current_sum - target_sum) หรือไม่

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

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

void printSubArray(int arr[], int i, int j) {
    cout << "{ ";
    for (; i <= j; i++)
        cout << arr[i] << " ";
    cout << "}";
}

void findSubArrayWithSum(int arr[], int n, int sum) {
    unordered_map<int, int> map;
    int curr_sum = 0;
    
    for (int i = 0; i < n; i++) {
        curr_sum = curr_sum + arr[i];
        
        if (curr_sum == sum) {
            cout << "SubArray with the given sum :";
            printSubArray(arr, 0, i);
            return;
        }
        
        if (map.find(curr_sum - sum) != map.end()) {
            cout << "SubArray with the given sum : ";
            printSubArray(arr, map[curr_sum - sum] + 1, i);
            return;
        }
        
        map[curr_sum] = i;
    }
    
    cout << "No subarray found!";
}

int main() {
    int arr[] = { 2, 5, -1, 4, 6, 9, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = 14;
    findSubArrayWithSum(arr, n, sum);
    return 0;
}

ผลลัพธ์

SubArray with the given sum : { 5 -1 4 6 }