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

HelKyle 發(fā)布于2019-08-16 13:50 / 1483人閱讀

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 isn"t one, return 0 instead.

Example:

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.
Follow up:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

Solution

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int i = 0, j = 0, sum = 0, min = Integer.MAX_VALUE;
        
        while (i <= j && j < nums.length) {
            sum += nums[j];
            while (sum >= target && i <= j) {
                min = Math.min(min, j-i+1);
                sum -= nums[i];
                i++;
            }
            j++;
        }
        
        return min == Integer.MAX_VALUE ? 0 : min;
    }
}

GPU云服務(wù)器云服務(wù)器 subarray Minimum ve asp209

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

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

相關(guān)文章

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

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

jas0n 2019-08-16 18:31 評論0 收藏0
LeetCode 209：最小長度的子數(shù)組 Minimum Size Subarray Sum

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

JayChen 2019-07-31 11:27 評論0 收藏0
LeetCode 209：最小長度的子數(shù)組 Minimum Size Subarray Sum

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

wow_worktile 2019-08-16 18:28 評論0 收藏0
LeetCode 209：最小長度的子數(shù)組 Minimum Size Subarray Sum

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

Vixb 2019-07-31 11:25 評論0 收藏0
[Leetcode] Minimum Size Subarray Sum 最短子串和

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

wthee 2019-08-14 16:15 評論0 收藏0