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


  • 0

    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;
        }
    };
    

  • 0
    A

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


  • 0
    S
    This post is deleted!

  • 0

    @sabertazimi Please post, thanks!!


  • 0
    S
    This post is deleted!

  • 1

    How about

    [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]?
    

  • 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);
            }
    
            if(nums.size()>7&&sum[0]==0&&sum.size()==1)//add this 
                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


Log in to reply
 

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