法算day10

[up主专用，视频内嵌代码贴在这]

和为k的子数组

问题描述

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。

  • 示例 1：
    输入：nums = [1,1,1], k = 2
    输出：2

  • 示例 2：
    输入：nums = [1,2,3], k = 3
    输出：2

提示：
1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

算法思路

这个问题的关键在于理解前缀和的概念：

  1. 前缀和是指从数组起始位置到当前位置的所有元素之和
  2. 如果从位置 i 到位置 j 的子数组和为 k，那么 prefix_sum[j] - prefix_sum[i-1] = k
  3. 可以转化为 prefix_sum[j] - k = prefix_sum[i-1]

python版（前缀和+哈希表）

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
def subarraySum(nums, k):
    """
    统计数组中所有和为k的连续子数组的个数
    
    参数:
        nums: 整数数组
        k: 目标和
    
    返回:
        count: 和为k的连续子数组的个数
    """
    # 初始化前缀和字典，记录每个前缀和出现的次数
    # 初始时前缀和为0出现1次，表示空数组的情况
    prefix_sum_count = {0: 1}
    
    # 初始化当前前缀和
    current_sum = 0
    
    # 初始化计数器
    count = 0
    
    # 遍历数组中的每个元素
    for num in nums:
        # 更新当前前缀和
        current_sum += num
        
        # 检查是否存在一个前缀和，使得 current_sum - 该前缀和 = k
        # 如果存在，说明从该前缀和位置到当前位置的子数组和为k
        if current_sum - k in prefix_sum_count:
            count += prefix_sum_count[current_sum - k]
        
        # 更新当前前缀和的出现次数
        if current_sum in prefix_sum_count: # 如果当前前缀和已经在字典中，
            prefix_sum_count[current_sum] += 1 # 则次数加1
        else:
            prefix_sum_count[current_sum] = 1 # 如果不存在，则初始化为1
    
    return count

# 测试代码
if __name__ == "__main__":
    # 示例1
    nums1 = [1, 1, 1]
    k1 = 2
    print(f"输入: nums = {nums1}, k = {k1}")
    print(f"输出: {subarraySum(nums1, k1)}")  # 输出: 2
    
    # 示例2
    nums2 = [1, 2, 3]
    k2 = 3
    print(f"输入: nums = {nums2}, k = {k2}")
    print(f"输出: {subarraySum(nums2, k2)}")  # 输出: 2
    
    # 额外测试用例
    nums3 = [1, 3, 2,4,5,6]
    k3 = 6
    print(f"输入: nums = {nums3}, k = {k3}")
    print(f"输出: {subarraySum(nums3, k3)}")  # 输出: 3

✅ 说明：

  • 时间复杂度: O(n)，只需要遍历数组一次
  • 空间复杂度: O(n)，最坏情况下需要存储n个不同的前缀和

疑点：为什么需要初始化 {0: 1}

初始化 prefix_sum_count = {0: 1} 是为了处理从数组开头开始的子数组：

  • 当子数组从索引0开始时，prefix_sum[i-1] 实际上不存在
  • 我们可以将其视为前缀和为0，出现在索引-1位置
  • 这样就能统一处理所有情况

示例说明：nums3 = [1, 3, 2, 4, 5, 6], k3 = 6

  • 初始状态
    1
    2
    3
    4
    5
    nums = [1, 3, 2, 4, 5, 6]
    k = 6
    prefix_sum_count = {0: 1}  # 初始前缀和字典，0出现1次
    current_sum = 0
    count = 0
  • 第1次循环 (i=0, num=1)
    1
    2
    3
    4
    5
    6
    7
    8
    当前元素: nums[0] = 1
    更新当前前缀和: current_sum = 0 + 1 = 1

    检查是否存在 current_sum - k = 1 - 6 = -5 在 prefix_sum_count 中
    - -5 不在字典中，所以 count 不变 (count=0)

    更新前缀和字典: prefix_sum_count[1] = 1
    现在 prefix_sum_count = {0: 1, 1: 1}
  • 第2次循环 (i=1, num=3)
    1
    2
    3
    4
    5
    6
    7
    8
    当前元素: nums[1] = 3
    更新当前前缀和: current_sum = 1 + 3 = 4

    检查是否存在 current_sum - k = 4 - 6 = -2 在 prefix_sum_count 中
    - -2 不在字典中，所以 count 不变 (count=0)

    更新前缀和字典: prefix_sum_count[4] = 1
    现在 prefix_sum_count = {0: 1, 1: 1, 4: 1}
    -第3次循环 (i=2, num=2)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    当前元素: nums[2] = 2
    更新当前前缀和: current_sum = 4 + 2 = 6

    检查是否存在 current_sum - k = 6 - 6 = 0 在 prefix_sum_count 中
    - 0 在字典中，出现次数为1
    - 所以 count += 1 → count = 1

    更新前缀和字典: prefix_sum_count[6] = 1
    现在 prefix_sum_count = {0: 1, 1: 1, 4: 1, 6: 1}
  • 第4次循环 (i=3, num=4)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    当前元素: nums[3] = 4
    更新当前前缀和: current_sum = 6 + 4 = 10

    检查是否存在 current_sum - k = 10 - 6 = 4 在 prefix_sum_count 中
    - 4 在字典中，出现次数为1
    - 所以 count += 1 → count = 2

    更新前缀和字典: prefix_sum_count[10] = 1
    现在 prefix_sum_count = {0: 1, 1: 1, 4: 1, 6: 1, 10: 1}
  • 第5次循环 (i=4, num=5)
    1
    2
    3
    4
    5
    6
    7
    8
    当前元素: nums[4] = 5
    更新当前前缀和: current_sum = 10 + 5 = 15

    检查是否存在 current_sum - k = 15 - 6 = 9 在 prefix_sum_count 中
    - 9 不在字典中，所以 count 不变 (count=2)

    更新前缀和字典: prefix_sum_count[15] = 1
    现在 prefix_sum_count = {0: 1, 1: 1, 4: 1, 6: 1, 10: 1, 15: 1}
  • 第6次循环 (i=5, num=6)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    当前元素: nums[5] = 6
    更新当前前缀和: current_sum = 15 + 6 = 21

    检查是否存在 current_sum - k = 21 - 6 = 15 在 prefix_sum_count 中
    - 15 在字典中，出现次数为1
    - 所以 count += 1 → count = 3

    更新前缀和字典: prefix_sum_count[21] = 1
    现在 prefix_sum_count = {0: 1, 1: 1, 4: 1, 6: 1, 10: 1, 15: 1, 21: 1}

java版

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.util.HashMap;
import java.util.Map;

public class SubarraySum {
    public int subarraySum(int[] nums, int k) {
        // 使用哈希表存储前缀和及其出现的次数
        // key: 前缀和, value: 该前缀和出现的次数
        Map<Integer, Integer> prefixSumCount = new HashMap<>();
        
        // 初始化：前缀和为0出现了1次（即不选择任何元素的情况）
        prefixSumCount.put(0, 1);
        
        int count = 0; // 记录满足条件的子数组个数
        int prefixSum = 0; // 当前前缀和
        
        // 遍历数组中的每个元素
        for (int num : nums) {
            // 计算当前的前缀和
            prefixSum += num;
            
            // 如果存在前缀和等于 (当前前缀和 - k)，说明找到了和为k的子数组
            // 因为：prefixSum - (prefixSum - k) = k
            if (prefixSumCount.containsKey(prefixSum - k)) {
                // 累加满足条件的子数组个数
                count += prefixSumCount.get(prefixSum - k);
            }
            
            // 更新当前前缀和的出现次数
            // 如果当前前缀和已经存在，次数+1；否则初始化为1
            prefixSumCount.put(prefixSum, prefixSumCount.getOrDefault(prefixSum, 0) + 1);
        }
        
        return count;
    }
    
    // 测试代码
    public static void main(String[] args) {
        SubarraySum solution = new SubarraySum();
        
        // 示例1
        int[] nums1 = {1, 1, 1};
        int k1 = 2;
        System.out.println("输入: nums = [1,1,1], k = 2");
        System.out.println("输出: " + solution.subarraySum(nums1, k1)); // 输出: 2
        
        // 示例2
        int[] nums2 = {1, 2, 3};
        int k2 = 3;
        System.out.println("输入: nums = [1,2,3], k = 3");
        System.out.println("输出: " + solution.subarraySum(nums2, k2)); // 输出: 2
        
        // 额外测试用例
        int[] nums3 = {1, -1, 0};
        int k3 = 0;
        System.out.println("输入: nums = [1,-1,0], k = 0");
        System.out.println("输出: " + solution.subarraySum(nums3, k3)); // 输出: 3
    }
}