问题描述

  1. 给定一个整数数组和一个整数K，返回该数组中和为k的连续子数组的个数
  2. https://leetcode-cn.com/problems/subarray-sum-equals-k/

实现

  1. 暴力枚举法,O(n*n)
  2. 利用HashMap数据结构进行优化
    • 遍历数组中的所有元素 $nums[i]$， 并统计以 $nums[i]$ 结尾的，和为 $k$ 的连续子数组的个数，求和可得所有和为 $k$ 的连续子数组个数。
    • 定义 $pre[i]$ 为 $[0,..,i]$ 所有元素的和，则“统计以 $nums[i]$ 结尾的，和为 $k$ 的连续子数组的个数”可转换为“统计满足 $pre[j] = pre[i]-k$ 的 $j$ 的个数”。
    • 利用哈希表，以 $pre[j]$ 为 key， 以个数为value，可以加速上述步骤的进行。