Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 주어진 합계로 부분배열 찾기 - (음수가 아닌 숫자)

<시간/>

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

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

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

설명 -

Subarray sum = 1 + 4 + 6 = 11

솔루션 접근 방식

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

알고리즘

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

문제를 해결하는 더 좋은 방법은 슬라이딩 창과 유사한 방법을 사용하는 것이지만 여기서는 가변 창을 사용합니다. 배열의 첫 번째 요소부터 시작하여 합계가 주어진 합계보다 커질 때까지 창에 요소를 추가합니다. 보다 커지면 다시 합보다 작아질 때까지 요소를 제거합니다. 전체 배열이 순회될 때까지 이 과정을 수행하십시오.

임의의 지점에서 창 합이 주어진 합과 같아지면 하위 배열을 인쇄합니다. 그리고 주어진 합계와 동일한 합계가 없고 순회할 요소가 없으면 "No subarray found!"를 인쇄합니다. .

알고리즘

초기화 - windowSum =0, 인덱스 =0, endindex =0

  • 1단계 − endindex를 사용하여 배열을 탐색합니다.

    • 1.1단계 − windowSum이 합계보다 커질 때까지 요소를 추가하여 windowSum을 업데이트합니다(예:if(windowSum windowSum =windowSum + arr[endIndex].

    • 1.2단계 − windowSum이 sum보다 크면 while(windowSum windowSum =windowSum - arr[endIndex]와 같은 요소를 제거하여 창 크기를 줄입니다.

    • 1.3단계 − windowSum ==합계인 경우 하위 배열을 인쇄합니다.

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