หาจำนวนซับอาร์เรย์ที่มีผลรวมอยู่ในช่วงที่กำหนดด้วย C++

ในบทความนี้ เราจะแก้ปัญหาการหาจำนวนซับอาร์เรย์ที่มีผลรวมอยู่ในช่วงที่กำหนด โดยใช้โปรแกรม C++ โจทย์ให้มาอาร์เรย์ arr[] ของจำนวนเต็มบวก และช่วง {L, R} เราต้องคำนวณจำนวนซับอาร์เรย์ทั้งหมดที่มีผลรวมอยู่ในช่วง L ถึง R ตัวอย่างดังนี้:

Input : arr[] = {1, 4, 6}, L = 3, R = 8 Output : 3 ซับอาร์เรย์คือ {1, 4}, {4}, {6}
Input : arr[] = {2, 3, 5, 8}, L = 4, R = 13 Output : 6 ซับอาร์เรย์คือ {2, 3}, {2, 3, 5}, {3, 5}, {5}, {5, 8}, {8}

วิธีการแก้ปัญหา

เราจะอธิบายสองวิธีในการแก้ปัญหานี้ด้วย C++:

1. วิธี Brute Force

วิธีพื้นฐานที่สุดคือ คำนวณผลรวมของซับอาร์เรย์ทุกชุด แล้วตรวจสอบว่าผลรวมนั้นอยู่ในช่วงที่กำหนดหรือไม่ (แต่วิธีนี้ใช้เวลามาก เพราะความซับซ้อนด้านเวลาคือ O(n²) โดย n คือขนาดอาร์เรย์)

2. วิธีที่มีประสิทธิภาพ (Efficient Approach - Sliding Window)

เพื่อประหยัดเวลา เราใช้วิธีที่เรียกว่า Efficient Approach ซึ่งใช้เทคนิค Sliding Window ช่วยให้คำนวณผลลัพธ์ได้เร็วขึ้นใน O(n)

ตัวอย่างโค้ด

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

int subCount(int *arr, int n, int x) {
    int start = 0, end = 0, sum = 0, count = 0;
    while (end < n) { // เลื่อนขอบขวาในลูปนี้
        sum = sum + arr[end];
        while(start <= end && sum >= x) { // ลูปนี้เลื่อนขอบซ้าย
            sum = sum - arr[start]; // ลดผลรวมขณะเลื่อนขอบซ้าย
            start++; // เลื่อนขอบซ้าย
        }
        count = count + ((end - start) + 1); // นับซับอาร์เรย์
        end++;
    }
    return count;
}

int main() {
    int n; // ขนาดอาร์เรย์
    int L, R;
    cin >> n;
    int arr[n];
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    cin >> L >> R;
    int answer;
    answer = subCount(arr, n, R) - subCount(arr, n, (L - 1)); // คำตอบสุดท้าย
    cout << answer << "\n";
    return 0;
}

ผลลัพธ์

1

คำอธิบายโค้ด

ในวิธีนี้ เรานับจำนวนซับอาร์เรย์ที่มีผลรวมน้อยกว่าขีดจำกัดบน (R) ของช่วงที่กำหนด แล้วลบด้วยจำนวนซับอาร์เรย์ที่มีผลรวมน้อยกว่าขีดจำกัดล่าง (L-1) โดยใช้ฟังก์ชัน subCount

ฟังก์ชัน subCount

ฟังก์ชันนี้ใช้เทคนิค Sliding Window เพื่อหาจำนวนซับอาร์เรย์ที่มีผลรวมน้อยกว่า x

เริ่มต้นให้ 'end' และ 'start' เท่ากับ 0 เมื่อเดินทางผ่านอาร์เรย์ เราจะรักษาผลรวมของสมาชิกจาก start ถึง end หลังจากนั้น หาก start เท่ากับ end และผลรวมมากกว่าหรือเท่ากับ x เราจะเริ่มเลื่อน start และลดผลรวมลง (เพราะนำสมาชิกออกจากผลรวม) จนกว่าผลรวมจะน้อยกว่า x หรือ start จะมากกว่า end ตอนนี้เราเพิ่มจำนวนซับอาร์เรย์เข้าไปใน count แล้วเพิ่มขอบขวา 1 เมื่อลูปภายนอกสิ้นสุด เราจะคืนค่าจำนวนซับอาร์เรย์ทั้งหมด

สรุป

ในบทความนี้ เราแก้ปัญหาการหาจำนวนซับอาร์เรย์ที่มีผลรวมอยู่ในช่วงที่กำหนด ด้วยความซับซ้อนด้านเวลา O(n) โดยใช้เทคนิค Sliding Window เรายังเรียนรู้โปรแกรม C++ สำหรับปัญหานี้ และวิธีการแก้ปัญหาทั้งแบบปกติและแบบมีประสิทธิภาพ สามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, Java, Python ได้เช่นกัน