滑动窗口类算法题

• 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