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

C++를 사용하여 왼쪽 배열의 합이 오른쪽 배열의 합과 같도록 배열에서 요소 찾기

<시간/>

배열 A가 있고 n개의 요소가 있다고 가정합니다. 우리의 임무는 배열 A를 두 개의 하위 배열로 나누어 각 하위 배열의 합이 같도록 하는 것입니다. 배열 A =[2, 3, 4, 1, 4, 5]라고 가정하고 출력은 1이므로 1 이전과 1 이후의 하위 배열이 사용됩니다. [2, 3, 4] 및 [4, 5].

이 문제를 해결하기 위해 right_sum의 첫 번째 요소를 제외한 전체 배열을 계산합니다. 그것이 파티션 요소라고 생각하십시오. 우리는 왼쪽에서 오른쪽으로 횡단할 것입니다. right_sum에서 요소를 빼고 left_sum에 요소를 추가하면 right_sum =left_sum인 점을 취합니다.

예시

#include<iostream>
using namespace std;
int getPartitionElement(int arr[], int size) {
   int right = 0, left = 0;
   for (int i = 1; i < size; i++)
      right += arr[i];
      for (int i = 0, j = 1; j < size; i++, j++) {
         right -= arr[j];
         left += arr[i];
         if (left == right)
            return arr[i + 1];
      }
   return -1;
}
int main() {
   int arr[] = { 2, 3, 4, 1, 4, 5 };
   int size = sizeof(arr) / sizeof(arr[0]);
   cout << "Partition element: " << getPartitionElement(arr, size);
}

출력

Partition element: 1