560_和为K的子数组.md

和为k的子数组

560. 和为K的子数组 - 力扣（LeetCode） (leetcode-cn.com)

分析

前缀和详解请看这里。

1. 前缀和

要找到数字连续的子数组和为k，即要找到num[i...j]的和为k。

令pre储存数组的前缀和。如果num[i...j]的和为k，即要求pre[j + 1] - pre[i] = k，即我们要找到前缀和中是否有前缀的和等于pre[j + 1] - k。

于是遍历数组，当前元素为nums[j]：

• 将当前元素添加到前缀和中：pre[j + 1] = pre[j] + nums[j]。
• 遍历前缀和数组：i : [0, j]，如果pre[i] = pre[j + 1] - k，说明nums[i...j]的和为k，个数加一。

最后返回记数结果即可。

时间复杂度为O(n^2)。

class Solution {
    public int subarraySum(int[] nums, int k) {
        int len = nums.length;
        int[] pre = new int[len + 1];
        int count = 0;
        for (int i = 0; i < len; i++) {
            pre[i + 1] = pre[i] + nums[i];
            int t = pre[i + 1] - k;
            for (int j = 0; j <= i; j++) {
                if (pre[j] == t) count++;
            }
        }
        return count;
    }
}

2. 哈希优化

对于遍历前缀和的操作：

for (int i = 0; i < len; i++) {
  	for (int j = 0; j <= i; j++) {
      if (pre[j] == t) count++;
    }
}

这里有O(n^2)的开销，考虑用哈希表储存前缀和的个数，直接通过哈希表获取，就能通过O(1)的时间复杂度得到。

总的时间复杂度为O(n)。

class Solution {
    public int subarraySum(int[] nums, int k) {
        int len = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int sum = 0;
        int count = 0;
        for (int i = 0; i < len; i++) {
            sum += nums[i];
            count += map.getOrDefault(sum - k, 0);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}