ในบทความนี้ เราจะหาจำนวนอาร์เรย์ย่อยที่มีผลรวมน้อยกว่า K โดยใช้ C++ ในปัญหานี้ เรามีอาร์เรย์ arr[] และจำนวนเต็ม K ดังนั้นตอนนี้เราต้องหาอาร์เรย์ย่อยที่มีผลรวมน้อยกว่า K นี่คือตัวอย่าง -
Input : arr[] = {1, 11, 2, 3, 15}
K = 10
Output : 4
{1}, {2}, {3} and {2, 3} แนวทางในการหาแนวทางแก้ไข
ตอนนี้เราจะใช้สองวิธีในการแก้ปัญหาที่กำหนด -
กำลังดุร้าย
ในแนวทางนี้ เราจะทำซ้ำผ่านอาร์เรย์ย่อยทั้งหมดและคำนวณผลรวมและเปรียบเทียบกับ k หากผลรวมน้อยกว่า k เพื่อเพิ่มคำตอบของเรา
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] = {1, 11, 2, 3, 15}; // given array
int k = 10; // given k
int size = sizeof(arr) / sizeof(int); // size of our array.
int ans = 0; // counter variable.
for(int i = 0; i < size; i++){ // outer loop.
int sum = 0;
for(int j = i; j < size; j++){ // inner loop.
sum = sum + arr[j];
if(sum < k) // comparing with k.
ans++; // incrementing our ans if sum is less than k.
}
}
cout << ans << "\n";
return 0;
} ผลลัพธ์
4
อย่างไรก็ตาม วิธีการนี้ไม่ค่อยดีนักเนื่องจากความซับซ้อนของเวลาสูงมาก O(N*N) โดยที่ n คือขนาดของอาร์เรย์ของเรา
เราจะพิจารณาทางเลือกอื่นโดยใช้วิธีหน้าต่างบานเลื่อน (ซึ่งจะช่วยเราลดความซับซ้อนของเวลาของโปรแกรม)
แนวทางที่มีประสิทธิภาพ
ไม่เหมือนกับ กำลังดุร้าย , เราจะไม่ผ่านอาร์เรย์ย่อยทั้งหมด แต่เราจะข้ามผ่านก็ต่อเมื่อผลรวมของอาร์เรย์ย่อยเกิน k และย้ายขอบด้านซ้ายจนถึงเส้นขอบด้านขวา และทำซ้ำต่อไปจนกว่าอาร์เรย์ทั้งหมดจะถูกข้าม
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] = {1, 11, 2, 3, 15}; // given array
int k = 10; // given k
int size = sizeof(arr) / sizeof(int); // size of our array.
int ans = 0; // counter variable.
int start = 0; // left border.
int end = 0; // right border.
int sum = 0;
while(end < size && start < size){ // till the whole array is traversed.
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
เราใช้ เทคนิคหน้าต่างบานเลื่อน เพื่อทำให้โปรแกรมของเราเร็วขึ้นหรือประหยัดเวลาในการทำงานสำหรับข้อจำกัดที่ใหญ่กว่าในแนวทางนี้
คำอธิบายของโค้ดด้านบน
ในแนวทางนี้ ปกติเราจะเดินทางจนถึงผลรวมของเราน้อยกว่า k และเพิ่มคำตอบตามนั้น ตอนนี้คือการเปลี่ยนแปลงที่สำคัญในโค้ดที่เกิดขึ้นเมื่อผลรวมมากกว่าหรือเท่ากับ k ในสถานการณ์นี้ เราเริ่มเพิ่มขอบด้านซ้ายให้เล็กลงจนถึงขอบด้านขวา หรือจนกว่าผลรวมจะมากกว่าหรือเท่ากับ k ขณะที่เราดำเนินการต่อไป มันจะข้ามผ่านอาร์เรย์ย่อยอื่นๆ ที่สามารถเกิดขึ้นได้ อาร์เรย์ย่อยใหม่เหล่านี้ซึ่งผลรวมน้อยกว่า k ถูกเพิ่มลงในคำตอบของเรา ดังนั้นคำตอบของเราจึงเพิ่มขึ้น
วิธีนี้มีประสิทธิภาพมากเมื่อเทียบกับ กำลังดุร้าย . รุ่นก่อนหน้า เราใช้เนื่องจากความซับซ้อนของเวลาคือ O(N) โดยที่ N คือขนาดของอาร์เรย์ของเรา
บทสรุป
ในบทความนี้ เราจะแก้ปัญหาเพื่อค้นหา Number of subarrays ที่มีผลรวมน้อยกว่า k โดยใช้ Sliding Window Technique . นอกจากนี้เรายังได้เรียนรู้โปรแกรม C ++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ ( Normal และ มีประสิทธิภาพ ) โดยที่เราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ หวังว่าบทความนี้จะเป็นประโยชน์
