ในบทความนี้ เราจะแก้จำนวนอาร์เรย์ย่อยที่มีผลรวมในช่วงที่กำหนดโดยใช้โปรแกรม C++ เรามีอาร์เรย์ arr[] ของจำนวนเต็มบวก และช่วง {L, R} และเราต้องคำนวณจำนวนทั้งหมดของอาร์เรย์ย่อยที่มีผลรวมในช่วงที่กำหนดจากรูปแบบ L ถึง R ดังนั้นนี่คือตัวอย่างง่ายๆ สำหรับปัญหา:
Input : arr[] = {1, 4, 6}, L = 3, R = 8
Output : 3
The subarrays are {1, 4}, {4}, {6}.
Input : arr[] = {2, 3, 5, 8}, L = 4, R = 13
Output : 6
The subarrays are {2, 3}, {2, 3, 5}, {3, 5},
{5}, {5, 8}, {8}. แนวทางในการหาแนวทางแก้ไข
เราจะอธิบายสองวิธีในการแก้ปัญหานี้โดยใช้ปัญหา C++ -
แนวทางกำลังเดรัจฉาน
แนวทางพื้นฐานที่สุดที่ใช้ในการคำนวณหาผลรวมของอาร์เรย์ย่อยทั้งหมด จากนั้นค้นหาว่าผลรวมนั้นอยู่ในช่วงที่กำหนดหรือไม่ (แต่วิธีนี้จะทำให้เราเสียเวลามากเนื่องจากความซับซ้อนของเวลาคือ O(n*n) โดยที่ n คือขนาดของอาร์เรย์)
แนวทางที่มีประสิทธิภาพ
เพื่อประหยัดเวลา เราใช้วิธีการอื่นที่เรียกว่าวิธีที่มีประสิทธิภาพ ตอนนี้วิธีที่มีประสิทธิภาพคือการใช้เทคนิคหน้าต่างบานเลื่อน โดยใช้เทคนิคนี้ เราจะคำนวณผลลัพธ์ของเราเร็วขึ้นหรือมีประสิทธิภาพมากขึ้นใน 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){ // we will be moving right border in this loop
sum = sum + arr[end];
while(start <= end && sum >= x){ // this loop will move our left border
sum = sum - arr[start]; // we will decrement sum while moving left border.
// For excluding the previous elements.
start++; // and move the left border.
}
count = count + ((end - start) + 1); // counting the subarrays.
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)); // Final Answer.
cout << answer << "\n";
return 0;
} ผลลัพธ์
3
คำอธิบายของโค้ดด้านบน
ในแนวทางนี้ เรากำลังนับจำนวนอาร์เรย์ย่อยโดยมีผลรวมน้อยกว่าขีดจำกัดบนของช่วงที่กำหนด จากนั้นเราจะลบจำนวนอาร์เรย์ย่อยที่ผลรวมน้อยกว่าขีดจำกัดล่างของช่วงที่กำหนดโดยใช้ฟังก์ชันการนับย่อย
ฟังก์ชันนับย่อย
ฟังก์ชันนี้ใช้เทคนิคหน้าต่างบานเลื่อนเพื่อค้นหาจำนวนอาร์เรย์ย่อยที่มีค่าน้อยกว่า x
ในตอนแรก เราเริ่มต้นด้วยทั้ง 'สิ้นสุดและเริ่มต้น' โดยมีค่า 0 เป็นค่าของมัน เมื่อเราสำรวจอาร์เรย์ เราจะรักษาผลรวมขององค์ประกอบตั้งแต่ต้นจนจบ หลังจากนั้น หากจุดเริ่มต้นเท่ากับจุดสิ้นสุดและผลรวมมากกว่าหรือเท่ากับ x เราจะเริ่มขยับจุดเริ่มต้นและค่อยๆ ลดจำนวนรวมของเราในขณะที่เรากำลังนำองค์ประกอบออกจากผลรวม
จนกระทั่งผลรวมของเราน้อยกว่า x หรือการเริ่มต้นของเรามากกว่าจุดสิ้นสุด ตอนนี้เราเพิ่มการนับด้วยการนับอาร์เรย์ย่อยแล้วเพิ่มเส้นขอบด้านขวาด้วย 1 ตอนนี้หลังจากที่วงรอบนอกสิ้นสุด เราจะคืนค่าจำนวนทั้งหมดของอาร์เรย์ย่อยของเรา
บทสรุป
ในบทความนี้ เราแก้ปัญหาเพื่อค้นหาจำนวนอาร์เรย์ย่อยที่มีผลรวมในช่วงที่กำหนดในความซับซ้อนของเวลา O(n) โดยใช้เทคนิคหน้าต่างบานเลื่อน นอกจากนี้เรายังได้เรียนรู้จากโปรแกรม C++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ (ปกติและมีประสิทธิภาพ) ซึ่งเราสามารถแก้ปัญหานี้ได้อย่างง่ายดาย เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python เป็นต้น
