Contents

[Golang][Leetcode][Array]刷題系列-209-Slide Window


209. Minimum Size Subarray Sum


Level : Medium

原題連結 : Click

題目 :

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, …, numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.


Example :

Note

Input: target = 7, nums = [2,3,1,2,4,3]

Output: 2

Explanation: The subarray [4,3] has the minimal length under the problem constraint.


以下是我自己的解法 - O(n)

Runtime: 4 ms, faster than 98.18% of Go online submissions for Minimum Size Subarray Sum.

解題思路 :

  • 首先題目要求給一個target,然後找尋相加之總和會大於等於他的"最短"&“連續"子數列

暴力解法 :

  • 我可以選擇用brute force solution直接開兩個for loop,針對每一個element去找到他能滿足以上條件所能回傳的子數列長度
  • Time Complexity會是O(n^2) Space Complexity為O(1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func minSubArrayLen(target int, nums []int) int {
 
    l := len(nums)
    
    result := l + 1
    
    
    for i := 0; i < l; i++ {
        
        sum := 0

        for j := i ; j < l; j++ {
            
            sum += nums[j]
            
            if sum >= target {
                
                if result > j - i + 1 {
                    
                    result = j - i + 1
                    
                    break
                }
            }
              
        }
    }
    
    if result == l + 1 {
        return 0
    }
    
    return result
}

Slide Window 解法 : 這其實也算是一個Two pointers的題目,但有用Slide window形容更貼切

  • 首先我們可以設兩個pointers,start & end
  • end負責往前進travel
  • start會停在原地每次都將end經過的element加起來直到滿足大於等於target的條件,我們就得到一個連續且大於等於target的子數列
  • 便做一次判斷去看是否小於我們手頭現有最小的子數列長度,如果滿足,便將他存入result變成我們暫時最好的答案
  • 這邊重點來了!! Slide window的精隨就是這時候要將start目前所在的element從sum中扣掉,再讓start往前走
  • 這時候用一個loop包裹著,讓start往前走後再做一次判斷是否現有sum依舊大於target..以此類推,直到sum小於target
  • 這時候才會退出loop,然後繼續end繼續往前走,直到sum滿足大於等於target,再繼續執行一樣的動作
  • 就如同滑動的窗口一般,每打開到一定的程度(也就是超過target時便開始一格一格關閉),尋找"最短"且"連續"且"sum大於等於target"的子數列
  • Time Complexity會是O(n) Space Complexity為O(1)
  • 不能看他一樣是兩個for loop就認為他也是O(n^2),其實可以先看包在裡面的loop,他就是不斷的關閉窗口,整個process也就只能關閉n次
  • 然後end就是打開窗口也就是打開n次,所以頂多就是O(2n)的時間 => 可以寫成O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
func minSubArrayLen(target int, nums []int) int {
    
    l := len(nums)
    
    sum := 0
    
    start := 0
    
    result := l + 1
    
    
    for end := 0; end < l; end++ {
        
        sum += nums[end]
        
        for sum >= target {
            
            if result > end - start + 1 {
                
                result = end - start + 1
                
            }
            
            sum -= nums[start]
            
            start++
            
        }
    }
    
    if result == l + 1 {
        return 0
    }
    
    return result
}

最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!