Split Array with Equal Sum (Leetcode 548)

這道題思路直接:就是先選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;
    }
};
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點(diǎn),簡書系信息發(fā)布平臺(tái),僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容