C++에서 주어진 합계로 하위 배열 찾기 - (음수 처리)

이 문제에서는 정렬되지 않은 순서로 저장된 N개의 정수로 구성된 배열 arr[]이 제공됩니다. 우리의 임무는 주어진 합계를 가진 부분배열을 찾는 것입니다. .

문제를 이해하기 위해 예를 들어 보겠습니다.

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

설명 -

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

솔루션 접근 방식

문제에 대한 간단한 해결책은 중첩 루프를 사용하는 것입니다. 배열을 반복하고 내부 루프를 사용하여 하위 배열을 찾습니다. 각 부분배열에 대해 모든 요소의 합을 찾아 주어진 합 값과 비교합니다. 같으면 부분배열을 인쇄합니다. 배열의 모든 요소가 순회되면 해당 배열을 찾을 수 없습니다.

알고리즘

• 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 }

문제를 해결하는 더 좋은 방법은 해시맵을 사용하는 것입니다. 해시맵은 현재 인덱스까지 접두사 합계를 저장합니다. 그리고 인덱스에 대해 합계가 있는 하위 배열이 있는지 확인합니다. 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 }