LeetCode 209-Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

題意

給出一個包含n個正整數(shù)的數(shù)組和一個正整數(shù)s晰赞,找到長度最小的(連續(xù))子數(shù)組使其和大于等于s。如果不存在這樣的子數(shù)組府蛇,返回0唐责。

比如數(shù)組為[2, 3, 1, 2, 4, 3]莱革,s = 7。子數(shù)組[4, 3]是長度最小的子數(shù)組,其和4+3≥7埠对。

分析

使用一種在線處理的方法术健,類似“數(shù)組的最大子數(shù)組和”的O(n)解法汹碱。

步驟

  • 我們設(shè)置bottom和top控制子數(shù)組的頭部和尾部。
  • 初始化bottom=0荞估,top為-1咳促,表示一個空的子數(shù)組稚新。
  • 子數(shù)組和sum=0,最小長度len=0跪腹。
  • 當(dāng)sum < s時褂删,在當(dāng)前子數(shù)組的尾部增加一個元素bottom[++top]。
  • 當(dāng)sum ≥ s時冲茸,去掉當(dāng)前子數(shù)組的頭部元素屯阀,并++bottom。
  • 退出循環(huán)的條件:top == nums.size() 或 bottom>top(此時已經(jīng)存在最小len為1轴术,不可能更小难衰,可以退出)。

算法復(fù)雜度

由于top和bottom至多遍歷一次數(shù)組nums膳音,因此算法復(fù)雜度為O(n)召衔。

更多練習(xí)

題目要求再給出一種O(nlogn)的解法。

簡略分析

采用分治法的思想祭陷。每次將區(qū)間A一分為二苍凛,成為A1和A2。子問題是求兩個子區(qū)間A1和A2中的各自的最小子數(shù)組長度len1和len2兵志,以及區(qū)間A的最小子數(shù)組長度len中的最小值醇蝴,即min{len1, len2, len}。

算法復(fù)雜度

主定理master定理)可知:T(n) = 2T(n/2) + n想罕,故算法復(fù)雜度為O(nlogn)*悠栓。

AC代碼

O(n)及O(nlogn)算法

//O(n)
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        if (!nums.size()) return 0;
        int bottom = 0, top = -1;
        int sum = 0, len = 0;
        while (true) {
            if (sum < s) {
                ++top;
                if (top != nums.size())
                    sum += nums[top];
                else
                    break;
            } else {
                sum -= nums[bottom]; ++bottom;
                if (bottom > top)
                    break;
            }
            if (sum >= s) {
                int new_len = top - bottom + 1;
                if (!len || len && new_len < len)
                    len = new_len;
            }
        }
        return len;
    }
};

//O(nlogn)
class Solution {
public:
    int MAX_INT = 999999999;
    int minSubArrayLen(int s, vector<int>& nums) {
        if (!nums.size()) return 0;
        return findMinLen(s, nums, 0, nums.size() - 1);
    }
    int findMinLen(int s, vector<int>& nums, int bottom, int top) {
        if (top == bottom) return nums[top] >= s ? 1 : 0;
        int mid = (bottom + top) / 2;
        int left = mid, right = mid + 1, sum = 0, len;
        while (sum < s && (right <= top || left >= bottom)) {
            if  (right > top) {
                sum += nums[left]; --left;
            }
            else if (left < bottom) {
                sum += nums[right]; ++right;
            }
            else if (nums[left] > nums[right]) {
                sum += nums[left]; --left;
            }
            else {
                sum += nums[right]; ++right;
            }
        }
        if (sum >= s) {
            len = right - left - 1;
            int leftLen = findMinLen(s, nums, bottom, mid);
            int rightLen = findMinLen(s, nums, mid + 1, top);
            return minValue(leftLen, rightLen, len);
        }
        else {
            return 0;
        }
    }
    int minValue(int x, int y, int z) {
        if (!x) x = MAX_INT;
        if (!y) y = MAX_INT;
        if (x <= y && x <= z) return x;
        if (y <= x && y <= z) return y;
        return z;
    }
};
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市按价,隨后出現(xiàn)的幾起案子惭适,更是在濱河造成了極大的恐慌,老刑警劉巖楼镐,帶你破解...
    沈念sama閱讀 222,729評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件癞志,死亡現(xiàn)場離奇詭異,居然都是意外死亡框产,警方通過查閱死者的電腦和手機(jī)凄杯,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來秉宿,“玉大人戒突,你說我怎么就攤上這事∶枘溃” “怎么了膊存?”我有些...
    開封第一講書人閱讀 169,461評論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長。 經(jīng)常有香客問我膝舅,道長嗡载,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,135評論 1 300
  • 正文 為了忘掉前任仍稀,我火速辦了婚禮洼滚,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘技潘。我一直安慰自己遥巴,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,130評論 6 398
  • 文/花漫 我一把揭開白布享幽。 她就那樣靜靜地躺著铲掐,像睡著了一般。 火紅的嫁衣襯著肌膚如雪值桩。 梳的紋絲不亂的頭發(fā)上摆霉,一...
    開封第一講書人閱讀 52,736評論 1 312
  • 那天,我揣著相機(jī)與錄音奔坟,去河邊找鬼携栋。 笑死,一個胖子當(dāng)著我的面吹牛咳秉,可吹牛的內(nèi)容都是我干的婉支。 我是一名探鬼主播,決...
    沈念sama閱讀 41,179評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼澜建,長吁一口氣:“原來是場噩夢啊……” “哼向挖!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起炕舵,我...
    開封第一講書人閱讀 40,124評論 0 277
  • 序言:老撾萬榮一對情侶失蹤何之,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后咽筋,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體溶推,經(jīng)...
    沈念sama閱讀 46,657評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,723評論 3 342
  • 正文 我和宋清朗相戀三年晤硕,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片庇忌。...
    茶點(diǎn)故事閱讀 40,872評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡舞箍,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出皆疹,到底是詐尸還是另有隱情疏橄,我是刑警寧澤,帶...
    沈念sama閱讀 36,533評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站捎迫,受9級特大地震影響晃酒,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜窄绒,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,213評論 3 336
  • 文/蒙蒙 一贝次、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧彰导,春花似錦蛔翅、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至掏父,卻和暖如春笋轨,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背赊淑。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評論 1 274
  • 我被黑心中介騙來泰國打工爵政, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人膏燃。 一個月前我還...
    沈念sama閱讀 49,304評論 3 379
  • 正文 我出身青樓茂卦,卻偏偏與公主長得像,于是被迫代替她去往敵國和親组哩。 傳聞我的和親對象是個殘疾皇子等龙,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,876評論 2 361

推薦閱讀更多精彩內(nèi)容