배열 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