我需要从具有以下属性的整数数组中识别变量的位置:
此变量前元素之和等于此变量后元素之和
如果变量不存在，我会显示一条消息。
例如，如果x = {1,2,4,2,1}，结果是4，位置是2，因为 1 + 2 == 2 + 1。
有什么建议么？在这个例子中很容易
if((x[0]+x[1])==(x[3]+x[4]))
print position 2
但是对于 n 个变量呢？
最佳答案
有几种方法可以做到这一点:
蛮力 - n/2 遍:
- 遍历数组。
- 对于每个元素，计算该元素前后的总和。
- 如果它们匹配，您就找到了该元素。
- 如果之前的总和大于之后的总和，则停止处理 - 未找到匹配项。
这对于较大的数组来说并不是很有效。
1.5 次通过:
- 计算所有元素的总和。
- 将该总和除以 2 (
half_sum)。 - 从头开始再次对元素求和，直到达到
half_sum。 - 检查您是否找到了有效元素。
单次通过(仅限正数):
- 保留两个运行总和:一个从开头 (
sum1)，一个从结尾 (sum2)。 - 设置
sum1 = 第一个元素和sum2 = 最后一个元素。 - 检查两者中最小的一个，并向其添加下一个/上一个元素。
- 循环直到位置相遇并检查元素是否为有效结果。
对于每种方法，您都必须先进行一些检查，看看数组是否不太小。
需要考虑的特殊情况:
- 空数组:返回false
- 只有 1 个元素的数组:返回元素
- 包含 2 个非零元素的数组:返回 false
- 中间全为零或零组怎么办？ (参见 Deduplicator 的评论)
- 负面因素:单次通过版本在这里不起作用(参见 Cris Luengo 的评论)
- 一般的负面因素:不可靠，考虑 +3 +1 -1 +1 -1 +3 +1(参见 Deduplicator 的评论)
关于c++ - vector 自定义总和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/51114286/