ค้นหาอาร์เรย์ย่อยที่มีผลรวมที่กำหนด - (จัดการตัวเลขติดลบ) ใน C++

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

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

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

คำอธิบาย −

Subarray sum = 5 - 1 + 4 + 6 = 14

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

วิธีแก้ปัญหาอย่างง่ายคือการใช้การวนซ้ำซ้อน เราจะวนรอบอาร์เรย์และใช้วงใน เราจะพบ 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 = 14;
   findSubArrayWithSum(arr, n, sum);
   return 0;
}

ผลลัพธ์

Subarray with given sum : { 5 -1 4 6 }

แนวทางที่ดีกว่าในการแก้ปัญหาคือการใช้แฮชแมป hashmap จะเก็บผลรวมคำนำหน้าจนถึงดัชนีปัจจุบัน และสำหรับดัชนีใด ๆ ให้ตรวจสอบว่ามี subarray ที่มีผลรวมหรือไม่ เราจะตรวจสอบว่ามีคำนำหน้าด้วย sum =sum - value หรือไม่

ตัวอย่าง

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

#include <bits/stdc++.h>
using namespace std;
void printSubArray(int arr[], int i, int j){
   cout<<"{ ";
      for(; i <= j; i++)
      cout<<arr[i]<<" ";
   cout<<"}";
}
void findSubArrayWithSum(int arr[], int n, int sum) {
   unordered_map<int, int> map;
   int curr_sum = 0;
   for (int i = 0; i < n; i++){
      curr_sum = curr_sum + arr[i];
      if (curr_sum == sum) {
         cout<<"SubArray with the given sum :";
         printSubArray(arr, 0, i);
         return;
      }
      if (map.find(curr_sum - sum) != map.end()) {
         cout<<"SubArray with the given sum : ";
         printSubArray(arr, map[curr_sum - sum] + 1 , i);
         return;
      }
      map[curr_sum] = i;
   }
   cout<<"No subarray found!";
}
int main() {
   int arr[] = { 2, 5, -1, 4, 6, 9, 3};
   int n = sizeof(arr) / sizeof(arr[0]);
   int sum = 14;
   findSubArrayWithSum(arr, n, sum);
   return 0;
}

ผลลัพธ์

SubArray with the given sum : { 5 -1 4 6 }