题目描述
给定一个长度为 n 的正整数数组 a1,a2,…,an。
你需要选择其中一个元素,将其移动至数组中的任意位置(也可以留在原位置)。
我们的目标是,在移动元素操作完成以后,将数组分为前后两个非空部分,并使前一部分的各元素之和等于后一部分的各元素之和。
请问,该目标能否达成?
输入格式
第一行包含整数 T,表示共有 T 组测试数据。
每组数据第一行包含整数 n。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
每组数据输出一行结果,目标可以达成,则输出 YES,否则输出 NO。
数据范围
$1≤T≤20,$
$1≤n≤105,$
$1≤ai≤109。$
同一测试点内所有 n 的和不超过 105。
样例
输入样例:
3
3
1 3 2
5
1 2 3 4 5
5
2 2 3 4 5
输出样例:
YES
NO
YES
算法1
(前缀和、哈希表) $O(n*log(n))$
blablabla
时间复杂度
$O(n*log(n))$
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
using namespace std;
typedef long long LL;
const int N = 100010;
LL a[N], b[N], s[N];
int n;
bool check(LL w[]) {
// 计算前缀和
for (int i = 1; i <= n; ++i) {
s[i] = s[i - 1] + w[i];
}
// 如果所有数字的总合不能二分,直接返回false
if (s[n] % 2 != 0) return false;
// set集合,用于快速查找是否有需要的元素O(log(n))
unordered_set<LL> S;
S.insert(0);
// 扫描一遍前缀和数组,如果当前位置的前缀和与总数一半的差值刚好在前面出现过
// 那么就说明把前面出现过的这个数放到后面可以刚好二分
// (不用绝对值,因为当前前缀和大于总数一半才有意义)
for (int i = 1; i <= n; ++i) {
S.insert(w[i]);
if (S.count(s[i] - s[n] / 2)) return true;
}
return false;
}
int main() {
int t;
cin >> t;
while (t -- ) {
cin >> n;
// 读入正序a数组和逆序b数组
for (int i = 1, j = n; i <= n; i ++, j -- ) {
cin >> a[i];
b[j] = a[i];
}
// 分别搜索正序前缀和以及逆序前缀和是否有符合题意的数字
if (check(a) || check(b)) puts("YES");
else puts("NO");
}
return 0;
}