前缀和+哈希表
(暴力枚举) $O(nlogn)$
题目含义就是寻找一个元素a[i]放到某个位置j(i>j)后可以得到数组中某个位置前缀和/后缀和==数组和/2
通过对满足前缀和/后缀和条件的位置的划分,可以发现共有三种情况
1.位置在j之前——>前缀和不受移动元素的影响,j前某个位置前缀和==s/2
2.位置在i之后——>后缀和不受移动元素的影响,i后某个位置的后缀和==s/2
3.位置在i与j之间——>从后缀和来看即要满足s[i]-a[i]==s[n]/2,(如果从前缀和s[i]+a[i]==s[n]/2)
上面三种情况可以用一个算式概括即s[i]-s[n]/2
为什么第三种情况一定要从后缀和来看呢
因为如果从前缀和来看没办法保证移动的元素与分割位置的相对关系(元素一定要在分割位置之后)
但是如果从后缀和来看的话,从前遍历,边遍历边插入哈希表,满足条件的w[i]一定位于分界之后
问题在于把过程复杂化了,移动元素考虑进了数组往后偏移一个单位的问题
但是对于判断条件来说,实际上并没有必要把这个细节问题考虑进去,这对判断条件不产生影响
因为可以通过把分割界限往后移一个单位达到同样的效果
#include<iostream>
#include<unordered_set>
using namespace std;
typedef long long LL;
const int N=100010;
int a[N],b[N];
int n;
bool check(int w[])
{
LL s[N];
unordered_set<LL> S;
for(int i=1;i<=n;i++)
s[i]=s[i-1]+w[i];
if(s[n]%2!=0) return false;
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;
for(int i=1,j=n;i<=n;i++,j--)
{
cin>>a[i];
b[j]=a[i];
}
if(check(a)||check(b)) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}