滑動窗口類演算法題

• 2020 年 4 月 25 日
• 筆記
• 演算法（go實現）

209. 長度最小的子數組

力扣地址

暴力破解思路

時間複雜度有點高，O(n3)，通不過測試，要進行優化

func minSubArrayLen(s int, nums []int) int {
    length := len(nums)
    min := length + 1
    for i := 0; i< length; i++{
        for j := i; j<length;j++{
            if j-i+1 >=min{
                break //這一趟已經沒必要找了
            }
            sum := 0
            for k := i;k<=j;k++{
                sum += nums[k]
            }
            if sum >= s{
                min = j-i+1
                break //這一趟已經找到，可以直接返回
            }
        }
    }

    //沒有找到滿足條件的連續子數組，返回0
    if min == length + 1{
        return 0
    }
    return min
}

暴力破解思路優化1

優化方向：暴力破解第三個for循環其實可以去除的，因為我們對[i,j]數組求和是一個連續的過程，是一個一個添加元素的，他們滿足sum[i,j] = sum[i,j-1] + nums[j].

func minSubArrayLen(s int, nums []int) int {
    length := len(nums)
    min := length + 1
    for i := 0; i< length; i++{
        sum := nums[i]
        for j := i; j<length;j++{
            if j-i+1 >=min{
                break //這一趟已經沒必要找了
            }
            if j > i{
               sum += nums[j]
            }
            if sum >= s{
                min = j-i+1
                break //這一趟已經找到，可以直接返回
            }
        }
    }

    //沒有找到滿足條件的連續子數組，返回0
    if min == length + 1{
        return 0
    }
    return min
}

暴力破解思路優化2

優化思路：第二個for循環還是可以加快點，因為數組和sum[i,j]是有序增加的，所以就想到二分查找的優化方法。

滑動窗口思路

func minSubArrayLen(s int, nums []int) int {
    //滑動窗口的解法：因為題目是一個連續子數組最小問題，滿足滑動窗口類型
    length := len(nums)
    l,r := 0,-1 // nums[l,r] 是我們的一個滑動窗口，默認是沒有元素
    sum := 0
    min := length +1 
    for l < length{
        if sum >= s{ //滑動窗口裡面和已經滿足要求，就不用繼續向右滑
            sum -= nums[l]
            l++
        }else if r+1<length{//可以允許右滑
            r++
            sum += nums[r]
        }else{
            break //滑動窗口不能右滑了，找不到，直接返回
        }

        if sum >= s && r-l+1 < min{
            min = r-l+1
        }
    }

    if min == length +1 {
        return 0
    }
    return min
}

3. 無重複字元的最長子串
4. Find All Anagrams in a String
5. 最小覆蓋子串 && 76. Minimum Window Substring