难度值:4
统计定界子数组的数目

滑动窗口

其实是属于双指针的一种 但这种题目特征更强
难度值:3
美观的花束
水果成篮

例1

美观的花束
原题链接:
https://leetcode.cn/problems/1GxJYY/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const MOD = 1e9 + 7


func beautifulBouquet(flowers []int, cnt int) int {
    h := map[int]int{}
    left := 0
    ans := 0
    
    for right,x := range flowers{
        h[x]++
        for h[x] > cnt{
            y := flowers[left]
            h[y]--
            if h[y] == 0{
                delete(h,y)
            }
            left++
        }
        ans = (ans + (right - left + 1) ) % MOD
    }
    return ans
}

例2

水果篮子
原题链接:
https://leetcode.cn/problems/fruit-into-baskets/

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
func max(a,b int)int{
    if a > b{
        return a
    }
    return b
}

func totalFruit(fruits []int) int {
    h := map[int]int{}
    left := 0
    ans := 0
    for right,x := range fruits{
        h[x]++
        for len(h) > 2{
            y := fruits[left]
            h[y]--
            if h[y] == 0{
                delete(h,y)
            }
            left++
        }
        ans = max(ans,right - left + 1)
    }
    return ans
}

例3

统计定界子数组的数量
原题链接:
https://leetcode.cn/problems/count-subarrays-with-fixed-bounds/

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
func max(a,b int) int{
    if a  > b {
        return a
    }
    return b
}

func min(a,b int)int{
    if a < b{
        return a
    }
    return b
}

func countSubarrays(nums []int, minK int, maxK int) int64 {
    i0,left,right := -1,-1,-1
    var ans int64
    for i,v := range nums{
        if v == minK{
            left = i 
        }
        if v == maxK{
            right = i
        }

        if v < minK || v > maxK{
            i0 = i
        }
        ans += int64( max(min(left,right) - i0,0))
    }
    return ans
}