C++ หาจำนวน Subarray ที่มีผลรวมอยู่ในช่วงที่กำหนด

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

Input : arr[] = {1, 4, 6}, L = 3, R = 8 Output : 3 Subarrays คือ {1, 4}, {4}, {6}
Input : arr[] = {2, 3, 5, 8}, L = 4, R = 13 Output : 6 Subarrays คือ {2, 3}, {2, 3, 5}, {3, 5}, {5}, {5, 8}, {8}

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

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

วิธี Brute Force

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

วิธีมีประสิทธิภาพ (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 arr[] = { 1, 4, 6 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int L = 3; 
    int R = 8; 
    int answer; 
    answer = subCount(arr, n, R) - subCount(arr, n, (L - 1)); 
    cout << answer << "\n"; 
    return 0; 
}

ผลลัพธ์

3

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

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

ฟังก์ชัน SubCount

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

เริ่มต้นเราเริ่มต้น 'end' และ 'start' ทั้งคู่เป็น 0 ขณะที่เราเดินผ่านอาร์เรย์ เราเก็บผลรวมของสมาชิกจาก start ถึง end หลังจากนั้น ถ้า start เท่ากับ end และผลรวมมากกว่าหรือเท่ากับ x เราเริ่มเลื่อน start และลดผลรวมลงเมื่อเราเอาสมาชิกออกจากผลรวม จนกว่าผลรวมจะน้อยกว่า x หรือ start จะมากกว่า end ตอนนี้เราเพิ่ม Count ด้วยจำนวน Subarray แล้วเพิ่ม Right Border ด้วย 1 หลังจาก Outer Loop จบ เราคืนค่าจำนวน Subarray ทั้งหมด

สรุป

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