No.281 - LeetCode[1013] Partition Array Into Three Parts With Equal Sum - 三子串和相等

这题有个坑,就是如果采用L->R 单向统计和为sum/3的子串时会存在:
A,B,C,D,E 5个子串和都为sum/3,看似是false,但是通过重新切分,可以变为
AB1, B2CD1, D2E 来组合成三个子串和为sum/3,见case71.

/*
 * @lc app=leetcode id=1013 lang=cpp
 *
 * [1013] Partition Array Into Three Parts With Equal Sum
 */

// @lc code=start
class Solution {
public:
    bool canThreePartsEqualSum(vector<int>& arr) {
        int N = arr.size();
        int sum = 0;
        for(int i=0;i<N;i++) sum += arr[i];
        if(sum % 3 != 0) return false;
        sum /= 3;
        int i = 0, j = N-1 , t;
        t = 0;
        for(;i<N;i++){
            t += arr[i];
            if(t == sum){
                break;
            }
        }
        t = 0;
        for(;j>=0;j--){
            t += arr[j];
            if(t == sum){
                break;
            }
        }
        if(i+1>=j) return false;
        t = 0;
        for(int k=i+1;k<j;k++){
            t += arr[k];
        }
        if(t == sum) return true;
        return false;
    }
};
// @lc code=end
上一篇:GO 自定义Cache


下一篇:b_lc_长度为 3 的不同回文子序列(统计两个相同字符中间有多少个不同字符)