LeetCode——和为K的子数组

NO.560 和为K的子数组中等

思路一：哈希表 假设一个数组子区间(l,r]和为K符合要求，则前r项元素-前l项元素=K，即前r项元素-K=前l项元素。

例如，[1,2,1,2,1]且k=3，区间(1,3]和为3，则索引3之前的元素和6-索引1之前的元素和3=3，即索引3之前的元素和6-3=索引1之前的元素和3。

所以可以遍历一遍数组，记录下前i项的和sum，用Map的健存储sum，Map的值存储sum出现的次数。初始化放入map:[0,1]，防止遗漏子数组，例如[3,-3]且k=0，如果没有初始化则遗漏。

假设当前扫到第i位，记录它的前i项和sum，用该和减去k，即sum-k，判断sum-k是否为某个位置的前n项和，若是，更新统计量。

如[1,2,1,2,1]且k=3，前0项和1入表，map不存在1-3；前1项和3入表，map存在3-3，计数器+map.get(0)；前2项和4入表，map存在4-3，计数器+map.get(1)；前3项和6入表，map存在6-3，计数器+map.get(3)；前4项和7入表，map存在7-3，计数器+map.get(4)；遍历结束，计数器为4。

public int subarraySum(int[] nums, int k) {
    //初始化
    HashMap<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);
    //前i项和sum，计数器count
    int sum = 0, count = 0;
    //遍历
    for (int i = 0; i < nums.length; i++) {
        //前i项和
        sum += nums[i];
        //存在
        if (map.containsKey(sum - k)) {
            count += map.get(sum - k);
        }
        map.put(sum, map.getOrDefault(sum, 0) + 1);
    }
    return count;
}

时间复杂度：O(n) 空间：O(n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.560 和为K的子数组 中等

NO.560 和为K的子数组中等