หา Subarray ที่มีผลรวมเท่ากับค่าที่กำหนด (เฉพาะตัวเลขไม่ติดลบ) ใน C++

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

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

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

คำอธิบาย

Subarray sum = 1 + 4 + 6 = 11

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

วิธีแก้ที่ง่ายคือการใช้ Nested Loop คล้ายกับกรณีที่มีตัวเลขลบ

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

• ขั้นตอนที่ 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 = 11;
    findSubArrayWithSum(arr, n, sum);
    return 0;
}

ผลลัพธ์

Subarray with given sum : { 1 4 6 }

วิธีที่ดีกว่า: ใช้ Sliding Window (หน้าต่างเลื่อน)

เนื่องจากอาร์เรย์มีแต่ตัวเลขไม่ติดลบ เราสามารถใช้เทคนิค Sliding Window ได้ เราจะเริ่มจากสมาชิกแรก เพิ่มสมาชิกเข้าไปในหน้าต่างจนกว่าผลรวมจะมากกว่าค่าที่กำหนด หากมากกว่า ให้ลดขนาดหน้าต่างโดยนำสมาชิกออกจากด้านซ้าย จนกว่าผลรวมจะน้อยกว่าหรือเท่ากับค่าที่กำหนด ทำซ้ำจนครบทุกสมาชิก

อัลกอริทึม Sliding Window

เริ่มต้น − windowSum = 0, sindex = 0, endindex = 0

• ขั้นตอนที่ 1 − เดินผ่านอาร์เรย์ด้วย endindex
  • ขั้นตอนที่ 1.1 − อัปเดต windowSum โดยเพิ่มสมาชิกจนกว่า windowSum จะมากกว่า sum
  • ขั้นตอนที่ 1.2 − หาก windowSum มากกว่า sum ให้ลดขนาดหน้าต่างโดยนำสมาชิกออก
  • ขั้นตอนที่ 1.3 − หาก windowSum == sum ให้พิมพ์ subarray
• ขั้นตอนที่ 2 − หากเดินครบทุกสมาชิกแล้วไม่พบ ให้พิมพ์ 'not possible'

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

#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 windowSum = arr[0], startIndex = 0, endIndex;
    for (endIndex = 1; endIndex <= n; endIndex++) {
        while (windowSum > sum && startIndex < endIndex - 1) {
            windowSum -= arr[startIndex];
            startIndex++;
        }
        if (windowSum == sum) {
            cout << "Subarray with given sum : ";
            printSubArray(arr, startIndex, endIndex);
            return 1;
        }
        if (endIndex < n)
            windowSum += arr[endIndex];
    }
    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 = 11;
    findSubArrayWithSum(arr, n, sum);
    return 0;
}

ผลลัพธ์

Subarray with given sum : { 1 4 6 }