固定中间

lc548

三指针——固定中间 预处理左右边

先算数组前缀和，用三个指针分四段区域

hash记录前两段相等的和

再找后两段和也相等且在哈希表中的情况

判断能否把数组分成和相等的四段

class Solution
{
public:
bool splitArray(vector<int>& nums)
{
int n = nums.size();
if (n < 7)
return false;
vector<int> presum(n + 1); //虚指
for (int i = 0; i < n; i++)
presum[i + 1] = presum[i] + nums[i];
// 3个指针,4个区域分别为 (1) L (2) M （3） R （4）
for (int M = 3; M < n - 3; M ++)
{
unordered_set<int> memo;
for (int L = 1; L < M - 1; L ++)
{ //找区域（1）和（2）相等的情况
int zoom1 = presum[L];
int zoom2 = presum[M] - presum[L + 1];
if (zoom1 == zoom2)
memo.insert(zoom1);
}
for (int R = M + 2; R < n - 1; R ++)
{ // (3)和（4）相等，且在memo中出现过（即==（1）==（2））
int zoom3 = presum[R] - presum[M + 1];
int zoom4 = presum[n] - presum[R + 1];
if (zoom3 == zoom4 && memo.count(zoom3))
return true;
}
}
return false;
}
};