成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專(zhuān)欄INFORMATION COLUMN

[Leetcode] Minimum Size Subarray Sum 最短子串和

wthee / 771人閱讀

摘要：雙指針復(fù)雜度時(shí)間空間思路我們用兩個(gè)指針維護(hù)一個(gè)窗口，保證這個(gè)窗口的內(nèi)的和是小于目標(biāo)數(shù)的。如果和仍小于目標(biāo)數(shù)，則將窗口右邊界右移。另外，如果左邊界大于右邊界時(shí)，說(shuō)明最短子串的長(zhǎng)度已經(jīng)小于等于，我們就不用再查找了。

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.
雙指針 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

我們用兩個(gè)指針維護(hù)一個(gè)窗口，保證這個(gè)窗口的內(nèi)的和是小于目標(biāo)數(shù)的。如果新來(lái)的數(shù)加上后，和大于目標(biāo)，則比較下當(dāng)前窗口長(zhǎng)度和最短窗口長(zhǎng)度，窗口左邊界右移。如果和仍小于目標(biāo)數(shù)，則將窗口右邊界右移。注意這里退出的條件，右邊界是小于等于長(zhǎng)度，因?yàn)槲覀兇翱诘搅俗钣覀?cè)時(shí)，還需要繼續(xù)左移左邊界來(lái)看有沒(méi)有更優(yōu)的解法。另外，如果左邊界大于右邊界時(shí)，說(shuō)明最短子串的長(zhǎng)度已經(jīng)小于等于1，我們就不用再查找了。

注意

循環(huán)的判斷條件是right <= nums.length && left <= right

代碼 
public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if(nums.length == 0) return 0;
        int left = 0, right = 0, sum = 0, minLen = nums.length + 1;
        while(right <= nums.length && left <= right){
            if(sum < s){
                // 當(dāng)右邊界等于長(zhǎng)度時(shí)，我們要多等一輪，等待左邊界左移，這時(shí)候不能加
                if(right < nums.length){
                    sum += nums[right];
                }
                right++;
            } else {
                // 當(dāng)和大于等于目標(biāo)時(shí)，檢查長(zhǎng)度并左移邊界
                minLen = Math.min(minLen, right - left);
                sum -= nums[left];
                left++;
            }
        }
        return minLen <= nums.length ? minLen : 0;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66174.html

相關(guān)文章

  • [LeetCode] 209. Minimum Size Subarray Sum (Easy ve

    Problem Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isnt one, return 0 instead. Example: Input: s =...

    HelKyle 評(píng)論0 收藏0

  • LeetCode 209：最小長(zhǎng)度的子數(shù)組 Minimum Size Subarray Sum

    摘要：如果不存在符合條件的連續(xù)子數(shù)組，返回。示例輸入輸出解釋子數(shù)組是該條件下的長(zhǎng)度最小的連續(xù)子數(shù)組。截取從索引到索引的數(shù)組，該數(shù)組之和若小于，則繼續(xù)后移，直到大于等于。記錄與差值返回的目標(biāo)數(shù)。之后后移一位繼續(xù)刷新新數(shù)組。 公眾號(hào)： 愛(ài)寫(xiě)bug（ID：icodebugs）作者：愛(ài)寫(xiě)bug 給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) s ，找出該數(shù)組中滿(mǎn)足其和 ≥ s 的長(zhǎng)度最小的連續(xù)子數(shù)組...

    jas0n 評(píng)論0 收藏0

  • LeetCode 209：最小長(zhǎng)度的子數(shù)組 Minimum Size Subarray Sum

    摘要：如果不存在符合條件的連續(xù)子數(shù)組，返回。示例輸入輸出解釋子數(shù)組是該條件下的長(zhǎng)度最小的連續(xù)子數(shù)組。截取從索引到索引的數(shù)組，該數(shù)組之和若小于，則繼續(xù)后移，直到大于等于。記錄與差值返回的目標(biāo)數(shù)。之后后移一位繼續(xù)刷新新數(shù)組。 公眾號(hào)： 愛(ài)寫(xiě)bug（ID：icodebugs）作者：愛(ài)寫(xiě)bug 給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) s ，找出該數(shù)組中滿(mǎn)足其和 ≥ s 的長(zhǎng)度最小的連續(xù)子數(shù)組...

    JayChen 評(píng)論0 收藏0

  • LeetCode 209：最小長(zhǎng)度的子數(shù)組 Minimum Size Subarray Sum

    摘要：如果不存在符合條件的連續(xù)子數(shù)組，返回。示例輸入輸出解釋子數(shù)組是該條件下的長(zhǎng)度最小的連續(xù)子數(shù)組。截取從索引到索引的數(shù)組，該數(shù)組之和若小于，則繼續(xù)后移，直到大于等于。記錄與差值返回的目標(biāo)數(shù)。之后后移一位繼續(xù)刷新新數(shù)組。 算法是一個(gè)程序的靈魂 公眾號(hào)：愛(ài)寫(xiě)bug（ID：icodebugs）作者：愛(ài)寫(xiě)bug 給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) s ，找出該數(shù)組中滿(mǎn)足其和 ≥ s 的...

    wow_worktile 評(píng)論0 收藏0

  • LeetCode 209：最小長(zhǎng)度的子數(shù)組 Minimum Size Subarray Sum

    摘要：如果不存在符合條件的連續(xù)子數(shù)組，返回。示例輸入輸出解釋子數(shù)組是該條件下的長(zhǎng)度最小的連續(xù)子數(shù)組。截取從索引到索引的數(shù)組，該數(shù)組之和若小于，則繼續(xù)后移，直到大于等于。記錄與差值返回的目標(biāo)數(shù)。之后后移一位繼續(xù)刷新新數(shù)組。 算法是一個(gè)程序的靈魂 公眾號(hào)：愛(ài)寫(xiě)bug（ID：icodebugs）作者：愛(ài)寫(xiě)bug 給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) s ，找出該數(shù)組中滿(mǎn)足其和 ≥ s 的...

    Vixb 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<