這道題思路直接:就是先選j梅屉,然后將數(shù)組分成兩部分舞竿。同時(shí)在每一部分中搀捷,一旦找到合適的 i,使得 sum(0, i-1) == sum(i+1, j-1)其馏,便用hashset記錄下來凤跑,然后再來選擇k. 同時(shí),建立presum數(shù)組叛复,來減少復(fù)雜度仔引。數(shù)組求連續(xù)和題,可以想建立一個(gè)presum數(shù)組
class Solution {
public:
bool splitArray(vector<int>& nums) {
if(nums.size() < 7) return false;
int n = nums.size();
vector<int> presum(n, 0);
presum[0] = nums[0];
for(int i=1; i<n; i++){
presum[i] = presum[i-1] + nums[i];
}
for(int j = 3; j < n - 3; j++){
unordered_set<int> st;
for(int i=1; i<j-1; i++){
if(presum[i-1] == presum[j-1] - presum[i]){
st.insert(presum[i-1]);
}
}
for(int k = j+2; k<n-1; k++){
if(presum[k-1] - presum[j] == presum[n-1] - presum[k]){
if(st.count(presum[k-1] - presum[j])) return true;
}
}
}
return false;
}
};