[数据结构与算法]第14题 力扣LeetCode 热题 HOT 100(560. 和为K的子数组)

第14题 力扣LeetCode 热题 HOT 100(560. 和为K的子数组)

题目

给定一个整数数组和一个整数 **k，**你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

说明 :

1. 数组的长度为 [1, 20,000]。
2. 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

题解

首先想到的当然是两重for循环，遍历得到两个节点之间的和，时间复杂度O(n^2)过不了，看了一眼数据范围，暴力过不了。。。想不出来优化方案，看了力扣的题解

时间复杂度O(n)的方案，遍历中累加得到当前下标的前缀和，然后把当前下标的前缀和用出现的次数表示，保存进哈希表中

就是遍历过程中，当遍历到某个下标时，当前元素和元素之前的数组中的元素构成一段。

这一段中分为两部分，其中是前面的一部分（从0开始到某个下标），后面一部分（某个下标后到当前遍历元素中的下标），要求后面一部分的和为目标值，即，前面一部分的值要求等于当前元素的前缀和减去目标值。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    let result = 0;
    // let sum = nums[0];
    let map = new Map();
    let arr = [];
    let sum=0;
    map.set(0,1);
    for(let i = 0; i< nums.length; i++){
        sum = sum+ nums[i];
        if(map.get(sum-k)){
           result= result+map.get(sum-k);
        };
        arr.push(sum);
        if(map.get(sum)){
            map.set(sum, map.get(sum)+1);
        }else{
            map.set(sum, 1);
        }
    }
    return result;
};