数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究用 C++ 在数组中查找一个元素，使得左数组的和等于右数组的和
假设我们有一个数组 A，其中包含 n 个元素。我们的任务是将数组 A 分成两个子数组，使得每个子数组的和相等。假设数组 A = [2, 3, 4, 1, 4, 5]，输出为 1，这样就取了以 1 为界限分割的前后子数组。即 [2, 3, 4] 和 [4, 5]。
要解决这个问题，我们要计算右和中除了第一个元素之外的整个数组。考虑这是分区元素。我们将从左到右遍历。从右和中减去一个元素，并将一个元素加到左和中，我们取其满足右和 = 左和的那个点。
示例
#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
更新于：2019-10-29
656 次浏览
广告