加强部门网站建设工作总结,网站建设模板推广,如何推销产品给客户,wordpress如何更改文章链接地址题目描述
给定一个整数数组和一个整数 k#xff0c;你需要找到该数组中和为 k 的连续的子数组的个数。示例 1 :输入:nums [1,1,1], k 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] #xff0c;且整…题目描述
给定一个整数数组和一个整数 k你需要找到该数组中和为 k 的连续的子数组的个数。示例 1 :输入:nums [1,1,1], k 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] 且整数 k 的范围是 [-1e7, 1e7]。来源力扣LeetCode
链接https://leetcode-cn.com/problems/subarray-sum-equals-k
著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。方法 1前缀和
思路
比较直白的想法是先构建前缀和数组 prefix计算以 i 结束的子数组的和然后在这个数组中找到所有满足条件的 [i, j] 区间也就是 prefix[j] - prefix[i] 等于 K。但这样找得两层循环了时间复杂度比较高。
有没有只需要遍历一遍数组的方法呢其实只要算一点点数学就好了
我们要找的一段区间 [i, j] 需要满足 prefix[j] - prefix[i] k (i j)。也就是当我们在遍历到 j 这个位置的时候只要往 j 的左边去找到有没有 prefix[i] 等于 prefix[j] - k 就行满足条件的 prefix[i] 可能有一个或多个哦。在遍历到 j 之前我们已经遍历过 i 了 (i j)所以我们只需要在遍历到 i 的时候用一个哈希表把 prefix[i] 存起来就能实现 O(1) 时间的查找。
其实我们连 prefix 数组都不需要因为我们在算出一个前缀和的时候就已经把它存到哈希表里面去了。所以可以只用一个变量 prefix 来计算前缀和在遍历 nums 数组的过程中不断更新 prefix同时检查 map[prefix - k] 是否在之前出现过。
复杂度分析
时间复杂度$O(n)$, n 为数组长度只扫描了一次数组。空间复杂度$O(n)$, n 为数组长度使用了一个哈希表来存每个前缀和出现的次数。
代码
JavaScript Code
/*** param {number[]} nums* param {number} k* return {number}*/
var subarraySum function (nums, k) {const map {};let count 0;let prefix 0;map[prefix] 1;for (let i 0; i nums.length; i) {prefix nums[i];if (prefix - k in map) {count map[prefix - k];}map[prefix] (map[prefix] || 0) 1;}return count;
};
