ค้นหา subarray ที่มีผลรวมที่กำหนด - (Nonnegative Numbers) ใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ซึ่งประกอบด้วยจำนวนเต็มบวก N จำนวนที่จัดเก็บในลำดับที่ไม่เรียงลำดับ งานของเราคือ ค้นหาอาร์เรย์ย่อยที่มีผลรวมที่กำหนด .

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

Input : arr[] = {2, 5, 1, 4, 6, 9, 5} sum = 11
Output : subarray = {1, 4, 6}

คำอธิบาย −

Subarray sum = 1 + 4 + 6 = 11

แนวทางการแก้ปัญหา

วิธีแก้ปัญหาอย่างง่ายคือการใช้การวนซ้ำซ้อน เราจะวนผ่านอาร์เรย์และใช้วงใน เราจะพบ subarray สำหรับแต่ละ subarray เราจะหาผลรวมขององค์ประกอบทั้งหมดและเปรียบเทียบกับค่ารวมที่กำหนด ถ้าเท่ากัน ให้พิมพ์ subarray หากองค์ประกอบทั้งหมดของอาร์เรย์ถูกสำรวจ ไม่พบอาร์เรย์ดังกล่าวพิมพ์

อัลกอริทึม

• ขั้นตอนที่ 1 − วนซ้ำอาร์เรย์ i -> 0 ถึง (n-1)

  • ขั้นตอนที่ 1.1 − สำหรับแต่ละองค์ประกอบ ให้หาผลรวมของอาร์เรย์ย่อยแต่ละรายการสำหรับอาร์เรย์ย่อยที่เป็นไปได้ทั้งหมด

  • ขั้นตอนที่ 1.2 − หากผลรวมขององค์ประกอบอาร์เรย์ผลรวมปัจจุบันเท่ากับอาร์เรย์ย่อยที่กำหนด ให้พิมพ์อาร์เรย์ย่อย

• ขั้นตอนที่ 2 − หากองค์ประกอบทั้งหมดของอาร์เรย์ถูกสำรวจและไม่พบอาร์เรย์ย่อย พิมพ์ "ไม่พบอาร์เรย์ย่อยที่มีผลรวมที่กำหนด!"

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#include <bits/stdc++.h>
using namespace std;
void printSubArray(int arr[], int i, int j){
   cout<<"{";
      for(; i < j; i++)
      cout<<arr[i]<<" ";
   cout<<"}";
}
int findSubArrayWithSum(int arr[], int n, int sum) {
   int currSum;
   for (int i = 0; i < n; i++) {
      currSum = arr[i];
      for (int j = i + 1; j <= n; j++) {
         if (currSum == sum) {
            cout<<"Subarray with given sum : ";
            printSumArray(arr, i, j); return 1;
         }
         if (currSum > sum || j == n)
         break;
         currSum = currSum + arr[j];
      }
   }
   cout<<"No subarray found";
   return 0;
}
int main() {
   int arr[] = { 2, 5, 1, 4, 6, 9, 3};
   int n = sizeof(arr) / sizeof(arr[0]);
   int sum = 11;
   findSubArrayWithSum(arr, n, sum);
   return 0;
}

ผลลัพธ์

Subarray with given sum : { 1 4 6 }

แนวทางที่ดีกว่าในการแก้ปัญหาคือการใช้วิธีการที่คล้ายกับหน้าต่างบานเลื่อน แต่ในที่นี้ เราจะมีหน้าต่างตัวแปร เราจะเริ่มจากองค์ประกอบแรกของอาร์เรย์ เพิ่มองค์ประกอบไปที่หน้าต่างจนกว่าผลรวมจะมากกว่าผลรวมที่กำหนด หากมีค่ามากกว่าให้ลบองค์ประกอบออกจนกว่าจะน้อยกว่าผลรวมอีกครั้ง ทำขั้นตอนนี้จนกว่าอาร์เรย์ทั้งหมดจะถูกข้ามไป

หาก ณ จุดใด ผลรวมของหน้าต่างจะเท่ากับผลรวมที่กำหนด ให้พิมพ์อาร์เรย์ย่อย และถ้าไม่พบหน้าต่างใดที่จะเท่ากับผลรวมที่กำหนดและไม่มีองค์ประกอบที่จะข้ามผ่าน ให้พิมพ์ "ไม่พบอาร์เรย์ย่อย!" .

อัลกอริทึม

เริ่มต้น − windowSum =0, sindex =0, endindex =0

• ขั้นตอนที่ 1 − สำรวจอาร์เรย์โดยใช้ endindex

  • ขั้นตอนที่ 1.1 อัปเดต windowSum โดยการเพิ่มองค์ประกอบจนกว่า windowSum จะมากกว่าผลรวม เช่น if(windowSum windowSum =windowSum + arr[endIndex].

  • ขั้นตอนที่ 1.2 − หาก windowSum มากกว่าผลรวม ให้ลดขนาดหน้าต่างโดยลบองค์ประกอบ เช่น while(windowSum windowSum =windowSum - arr[endIndex]

  • ขั้นตอนที่ 1.3 − ถ้า windowSum ==sum ให้พิมพ์ subarray

• ขั้นตอนที่ 2 − หากผ่านอาร์เรย์ ให้พิมพ์ -> 'ไม่สามารถทำได้'

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#include <bits/stdc++.h>
using namespace std;
void printSubArray(int arr[], int i, int j){
   cout<<"{ ";
      for(; i < j; i++)
      cout<<arr[i]<<" ";
   cout<<"}";
}
int findSubArrayWithSum(int arr[], int n, int sum) {
   int windowSum = arr[0], startIndex = 0, endIndex;
   for (endIndex = 1; endIndex <= n; endIndex++) {
      while (windowSum > sum && startIndex < endIndex - 1) {
         windowSum -= arr[startIndex];
         startIndex++;
      }
      if (windowSum == sum) {
         cout << "Subarray with given sum : ";
         printSumArray(arr, startIndex ,endIndex);
         return 1;
      }
      if (endIndex < n)
      windowSum += arr[endIndex];
   }
   cout << "No subarray found";
   return 0;
}
int main() {
   int arr[] = { 2, 5, 1, 4, 6, 9, 3};
   int n = sizeof(arr) / sizeof(arr[0]);
   int sum = 11;
   findSubArrayWithSum(arr, n, sum);
   return 0;
}

ผลลัพธ์

Subarray with given sum : { 1 4 6 }