题目大纲

力扣-209-长度最小的子数组
力扣-713-乘积小于K的子数组
力扣-1004-最大连续1的个数III
力扣-1234-替换子串得到平衡串
力扣-1658-将x减到0的最小操作数

思路讲解

同向双指针 滑动窗口【基础算法精讲 01】_哔哩哔哩_bilibili

长度最小的子数组

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 minSubArrayLen(target int, nums []int) int {
    minLen := len(nums)+1 // 这里保证初始量比最大值还大就行，还有一种方式是直接用math.MaxInt
    left := 0
    sum := 0

    for right:= 0; right < len(nums); right++ {
        sum = sum + nums[right]

        for sum >= target {
            nowLen := right-left+1
            if nowLen < minLen {
                minLen = nowLen
            }

            // 移动左指针
            sum = sum - nums[left]
            left++
        }
    }

    if minLen == len(nums)+1 {
        return 0
    }
    return minLen
}

乘积小于k的子数组

  • 核心点在于：假设左指针为left，右指针为right，则固定right点，所有满足条件的子数组数量为：right-left+1
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    func numSubarrayProductLessThanK(nums []int, k int) int {
        if k <= 1 {
            return 0
        }

        res := 0
        left := 0
        product := 1

        for right := 0; right < len(nums); right++ {
            product = product * nums[right]

            for product >= k {
                product = product/nums[left]
                left++
            }

            res = res + (right-left+1)
        }

        return res
    }

无重复字符的最小子串

使用简单map
  • 首先使用map保存right遍历过的节点，key为字符对应的字节，value为字节在字符串数组中的位置
  • 如果没有重复，则当前无重复结果now+1，并且把当前字符加入到map中
  • 如果有重复，则把left指针移动到重复节点的后面一个，并且需要删除原来left-》重复节点，最后把当前节点计入map
    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
    func lengthOfLongestSubstring(s string) int {
        if len(s) == 0 {
            return 0
        }

        strMap := make(map[byte]int, 0)
        left := 0
        now := 0
        max := 0

        for right:=0; right < len(s); right++ {
            if existIndex, ok := strMap[s[right]]; ok {
                for left < existIndex+1 {
                    delete(strMap, s[left])
                    left++
                }
                left = existIndex+1
                strMap[s[right]] = right
            } else {
                strMap[s[right]] = right
                now = right-left+1
                if now > max {
                    max = now
                }
            }
        }

        return max
    }
    image.png

有更好的做法》》》》》 hhhh, 是我看大佬教程学到的，上面是自己琢磨的。

使用map计数器
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func lengthOfLongestSubstring(s string) int {
    if len(s) == 0 {
        return 0
    }

    strCounter := make(map[byte]int, 0)
    left := 0
    max := 0

    for right := 0; right < len(s); right++ {
        strCounter[s[right]]++

        for strCounter[s[right]] > 1 {
            strCounter[s[left]]--
            left++
        }

        if right-left+1 > max {
            max = right-left+1
        }
    }

    return max
}

最大连续1的个数III

关键在于Counter的设计

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
func longestOnes(nums []int, k int) int {
    if len(nums) <= k {
        return len(nums)
    }

    left := 0
    maxLen := 0
    zeroCounter := make(map[int]int, 0)

    for right := 0; right < len(nums); right++ {
        zeroCounter[nums[right]]++

        if nums[right] == 0 {
            for zeroCounter[nums[right]] > k {
                zeroCounter[nums[left]]--
                left++
            }
        }

        if right-left+1 > maxLen {
            maxLen = right-left+1
        }
    }

    return maxLen
}

替换子串得到平衡串

  • 假设字符串长度为n
  • 如果Q/W/E/R的出现次数都等于n/4，则说明已经平衡了
  • 如果除了子串之外的字符Q/W/E/R的出现次数都小于或等于n/4，说明可以通过子串的填补来实现平衡；如果大于n/4则说明无法通过当前子串来实现平衡（因为你无法改变子串之外的字符，比如QQQ[QWERR]，子串QWERR之外的字符中Q出现了三次大于2，则你无论如何改变子串都无法实现平衡；反之，如果是这样的QQR[QWERR]，则可以将子串改变为[WWERE]=>QQRWWERE,便实现了平衡）。
    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
    func balancedString(s string) int {
        counter := make(map[byte]int, 0)
        for i := 0; i<len(s); i++ {
            counter[s[i]]++
        }
        left := 0
        m := len(s)/4
        min := math.MaxInt // 其实这个只是定义一个最大值

        // 如果WQER四个字符的个数恰好是m，则说明已经是平衡字符串了
        if counter['Q'] == m &&
            counter['W'] == m &&
              counter['E'] == m &&
                counter['R'] == m {
            return 0
        }

        for right:=0; right<len(s); right++ {
            // 属于子串范围的就应该减去
            counter[s[right]]--

            for counter['Q'] <= m &&
                    counter['W'] <= m &&
                        counter['E'] <= m &&
                            counter['R'] <= m {
                if right-left+1 < min {
                    min = right-left+1
                }
                counter[s[left]]++ // 移除了子串的范围就应该放到其他的里面， counter始终是维护子串之外的数据
                left++
            }
        }
        return min
    }
将X减到0的最小操作数
  • 其实这一题和上面：力扣-209-长度最小的子数组是一模一样的， 可以理解为和为allSum-x的最小子串，稍微变了一下而已
    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
    37
    38
    39
    func minOperations(nums []int, x int) int {
        left := 0
        min := math.MaxInt
        sum := 0

        allSum := 0
        for _, v := range nums {
            allSum = allSum + v
        }
        // 总和小于指定的值，肯定不符合
        if allSum < x {
            return -1
        }
        // 其实这一题可以转变一个思路，就是求满足子串总和=allSum-x的最小子串
        otherSum := allSum - x

        for right:=0; right<len(nums); right++ {
            sum = sum + nums[right]

            for sum > otherSum {
                sum = sum - nums[left]
                left++
            }

            if sum == otherSum {
                subNumsLen := right-left+1
                otherNumerLen := len(nums) - subNumsLen
                if otherNumerLen < min {
                    min = otherNumerLen
                }
            }
        }

        if min == math.MaxInt {
            min = -1
        }
        
        return min
    }