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

ในบทความนี้ เราจะหาจำนวนซับอาร์เรย์ (subarray) ที่มีผลรวมน้อยกว่าค่า K โดยใช้ภาษา C++ โจทย์ให้มาอาร์เรย์ arr[] และจำนวนเต็ม K เราต้องหาซับอาร์เรย์ที่มีผลรวมน้อยกว่า K ตัวอย่างดังนี้:

Input : arr[] = {1, 11, 2, 3, 15} K = 10 Output : 4 ซับอาร์เรย์คือ {1}, {2}, {3} และ {2, 3}

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

เราจะใช้สองวิธีที่แตกต่างกันในการแก้ปัญหานี้:

1. วิธี Brute Force (การค้นหาทุกกรณี)

ในวิธีนี้ เราจะวนลูปผ่านซับอาร์เรย์ทุกชุด คำนวณผลรวม และเปรียบเทียบกับ K หากผลรวมน้อยกว่า K ให้เพิ่มตัวนับคำตอบ

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

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

int main() {
    int arr[] = {1, 11, 2, 3, 15}; // อาร์เรย์ที่กำหนด
    int k = 10; // ค่า K ที่กำหนด
    int size = sizeof(arr) / sizeof(int); // ขนาดของอาร์เรย์
    int ans = 0; // ตัวนับคำตอบ
    
    for(int i = 0; i < size; i++) { // วนลูปภายนอก
        int sum = 0;
        for(int j = i; j < size; j++) { // วนลูปภายใน
            sum = sum + arr[j];
            if(sum < k) // เปรียบเทียบกับ K
                ans++; // เพิ่มคำตอบหากผลรวมน้อยกว่า K
        }
    }
    cout << ans << "\n";
    return 0;
}

ผลลัพธ์

4

อย่างไรก็ตาม วิธีนี้ไม่ค่อยดี เพราะมีความซับซ้อนด้านเวลา (Time Complexity) สูงมาก คือ O(N²) โดยที่ N คือขนาดของอาร์เรย์

เราจะมาดูวิธีแก้ปัญหาอีกวิธีหนึ่งที่ใช้เทคนิค Sliding Window (หน้าต่างเลื่อน) ซึ่งจะช่วยลดความซับซ้อนด้านเวลาได้

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

แตกต่างจาก Brute Force เราจะไม่ต้องตรวจสอบซับอาร์เรย์ทุกชุด แต่จะเลื่อนขอบซ้าย (left border) ก็ต่อเมื่อผลรวมของซับอาร์เรย์เกิน K และทำซ้ำจนครบทุกอาร์เรย์

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

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

int main() {
    int arr[] = {1, 11, 2, 3, 15}; // อาร์เรย์ที่กำหนด
    int k = 10; // ค่า K ที่กำหนด
    int size = sizeof(arr) / sizeof(int); // ขนาดของอาร์เรย์
    int ans = 0; // ตัวนับคำตอบ
    int start = 0; // ขอบซ้าย
    int end = 0; // ขอบขวา
    int sum = 0;
    
    while(end < size && start < size) { // วนจนครบทุกอาร์เรย์
        while(sum >= k && start < end) {
            sum = sum - arr[start];
            start++;
        }
        if(end >= start)
            ans = ans + end - start;
        sum += arr[end];
        end++;
    }
    cout << ans << "\n";
    return 0;
}

ผลลัพธ์

4

เราใช้ เทคนิค Sliding Window เพื่อทำให้โปรแกรมทำงานเร็วขึ้นและมีประสิทธิภาพด้านเวลาสำหรับข้อจำกัดขนาดใหญ่

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

ในวิธีนี้ เราเดินทางผ่านอาร์เรย์จนกว่าผลรวมจะมากกว่าหรือเท่ากับ K ซึ่งเป็นจุดสำคัญที่โค้ดเปลี่ยนแปลง เมื่อผลรวม ≥ K เราจะเริ่มเลื่อนขอบซ้าย (start) เข้าใกล้ขอบขวา (end) จนกว่าผลรวมจะน้อยกว่า K อีกครั้ง ขณะที่ดำเนินการต่อ เราจะผ่านซับอาร์เรย์อื่นๆ ที่สามารถสร้างได้ ซับอาร์เรย์ใหม่ที่มีผลรวมน้อยกว่า K จะถูกเพิ่มเข้าไปในคำตอบ

วิธีนี้มีประสิทธิภาพมากกว่าวิธี Brute Force อย่างมาก เนื่องจากความซับซ้อนด้านเวลาคือ O(N) โดยที่ N คือขนาดของอาร์เรย์

สรุป

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