[C++] Clean Code - Skip 0s (9 ms)

• There is a test case filled with a million 0s, so we do need to skip those extra consecutive 0s to accelerate,
..., 0, 0, 0, 0, ... is the same as one 0;

This solution runs 9ms

``````class Solution {
public:
bool splitArray(vector<int>& nums) {
vector<int> sum;
int prev = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == 0 && i > 0 && nums[i - 1] == 0)  continue; // skip extra 0s to accelerate
prev += nums[i];
sum.push_back(prev);
}

int n = sum.size();
for (int i = 1; i < n; i++) {
int sum1 = sum[i - 1];
for (int j = i + 2; j < n - 3; j++) {
int sum2 = sum[j - 1] - sum[i];
if (sum2 != sum1) continue;
for (int k = j + 2; k < n - 1; k++) {
int sum3 = sum[k - 1] - sum[j];
int sum4 = sum[n - 1] - sum[k];
if (sum2 == sum3 && sum3 == sum4) {
return true;
}
}
}
}

return false;
}
};
``````

This solution cached the matched quater result on the 1st half. But runs slightly slower. (19ms)

``````class Solution {
public:
bool splitArray(vector<int>& nums) {
vector<int> sum;
int prev = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == 0 && i > 0 && nums[i - 1] == 0)  continue; // skip extra 0s to accelerate
prev += nums[i];
sum.push_back(prev);
}

int n = sum.size();
for (int j = 3; j < n - 3; j++) {
set<int> subsums;
for (int i = 0; i < j - 1; i++) {
int sum1 = sum[i - 1];
int sum2 = sum[j - 1] - sum[i];
if (sum[i - 1] == sum[j - 1] - sum[i]) {
subsums.insert(sum1);
}
}

for (int k = j + 1; k < n - 1; k++) {
int sum3 = sum[k - 1] - sum[j];
int sum4 = sum[n - 1] - sum[k];
if (sum3 == sum4 && subsums.count(sum3)) {
return true;
}
}
}

return false;
}
};
``````

• @alexander will this still work if all the numbers are increased by 1?

• This post is deleted!

• @sabertazimi Please post, thanks!!

• This post is deleted!

``````[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]?
``````

• ``````class Solution {
public:
bool splitArray(vector<int>& nums) {
vector<int> sum;
int prev = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == 0 && i > 0 && nums[i - 1] == 0)  continue; // skip extra 0s to accelerate
prev += nums[i];
sum.push_back(prev);
}

return true;

int n = sum.size();
for (int i = 1; i < n; i++) {
int sum1 = sum[i - 1];
for (int j = i + 2; j < n - 3; j++) {
int sum2 = sum[j - 1] - sum[i];
if (sum2 != sum1) continue;
for (int k = j + 2; k < n - 1; k++) {
int sum3 = sum[k - 1] - sum[j];
int sum4 = sum[n - 1] - sum[k];
if (sum2 == sum3 && sum3 == sum4) {
return true;
}
}
}
}

return false;
}
};
``````

I modify your code , Does it work in all of case?.If I was wrong please let me know

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.