08. 找到符合确切条件的子数组数

0 - 算法, 0.0 - 算法模版 本文总阅读量次

正文

在算法面试中，“找到符合确切条件的子数组数”通常有两种核心解法：前缀和 + 哈希表（通用性最强）或 双指针/滑动窗口（适用于非负数序列）。

方案一：前缀和 + 哈希表 (通用模板)

这是解决该类问题的“银弹”，适用于数组中包含负数的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
fun numSubarraysWithSum(nums: IntArray, goal: Int): Int {
    var count = 0
    var prefixSum = 0
    // key: 前缀和的值, value: 该前缀和出现的次数
    val map = mutableMapOf<Int, Int>()
    // 初始化：前缀和为 0 已经出现过 1 次
    map[0] = 1

    for (num in nums) {
        prefixSum += num
        // 如果 prefixSum - goal 存在于 map 中，说明存在子数组和为 goal
        count += map.getOrDefault(prefixSum - goal, 0)
        // 更新当前前缀和的出现次数
        map[prefixSum] = map.getOrDefault(prefixSum, 0) + 1
    }

    return count
}

方案二：双指针 / 滑动窗口 (针对非负数优化)

如果数组中元素全部非负，使用滑动窗口可以将空间复杂度降低到 $O(1)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 统计和正好为 goal 的子数组数量
fun numSubarraysWithSumSlidingWindow(nums: IntArray, goal: Int): Int {
    // 技巧：正好为 K = 最多为 K - 最多为 K-1
    return atMost(nums, goal) - atMost(nums, goal - 1)
}

private fun atMost(nums: IntArray, goal: Int): Int {
    if (goal < 0) return 0
    var left = 0
    var sum = 0
    var count = 0
    for (right in nums.indices) {
        sum += nums[right]
        while (sum > goal) {
            sum -= nums[left]
            left++
        }
        // [left...right] 之间所有以 right 结尾的子数组都符合“和 <= goal”
        count += right - left + 1
    }
    return count
}

使用说明

  1. 为什么原模板中“统计连续的0”比较复杂？
    在滑动窗口中，如果存在 0，窗口的和不会改变，这会导致统计“确切”数量时变得棘手。“恰好为 K = 最多为 K - 最多为 K-1” 是处理此类滑动窗口问题最优雅的数学技巧。

  2. 核心优势：

    • 哈希表法：时间 $O(N)$，空间 $O(N)$。适用于任何数组。
    • 双指针法：时间 $O(N)$，空间 $O(1)$。仅适用于非负数组。

  3. 常见变形：

    • 求和为 K 的子数组。
    • 求奇数个数为 K 的子数组（将奇数看作 1，偶数看作 0）。
0 - 算法, 0.0 - 算法模版