[LeetCode] 560. Subarray Sum Equals K

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

Constraints:

The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

和为K的子数组。

题意是给一个数组和一个数字K，请求出input数组中有多少个子数组的和为K。两种做法，一种是暴力解；一种会用到hashmap。

暴力解的思路是用两个for loop扫描input数组，扫描的时候记录累加和sum，再用一个变量记录是否有满足条件的子数组满足sum == k，若有就++。

时间O(n^2)

空间O(1)

 1 /**
 2  * @param {number[]} nums
 3  * @param {number} k
 4  * @return {number}
 5  */
 6 var subarraySum = function (nums, k) {
 7     let res = 0;
 8     for (let i = 0; i < nums.length; i++) {
 9         let sum = 0;
10         for (let j = i; j < nums.length; j++) {
11             sum += nums[j];
12             if (sum === k) {
13                 res++;
14             }
15         }
16     }
17     return res;
18 };

hashmap的做法用到了前缀和的思想。

作者：LeetCode

链接：https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/he-wei-kde-zi-shu-zu-by-leetcode-solution/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

根据这个思路，我们可以用hashmap记录数组所有的前N项的前缀和。key是前缀和，value是这个前缀和出现的次数。扫描的时候，如果map存在sum - k，就说明有满足条件的子数组。因为数组可能存在负数的关系，加入前缀和的时候需要判断key是否存在过。举个例子，比如前N项的和是sum，前N-1项的和是sum - k，那么前N项的和 - 前N-1项的和 = K。

x, x, x, x, x, x, x, x - sum

x, x, x, x, x, x, x, k - presum - k

时间O(n)

空间O(n)

JavaScript实现

 1 /**
 2  * @param {number[]} nums
 3  * @param {number} k
 4  * @return {number}
 5  */
 6 var subarraySum = function (nums, k) {
 7     // corner case
 8     if (nums.length <= 0) return 0;
 9 
10     // normal case
11     let map = new Map([[0, 1]]);
12     let sum = 0;
13     let count = 0;
14     for (let i = 0; i < nums.length; i++) {
15         sum += nums[i];
16         if (map.has(sum - k)) {
17             count += map.get(sum - k);
18         }
19         if (!map.has(sum)) {
20             map.set(sum, 1);
21         } else {
22             map.set(sum, map.get(sum) + 1);
23         }
24     }
25     return count;
26 };

Java实现

 1 class Solution {
 2     public int subarraySum(int[] nums, int k) {
 3         int res = 0;
 4         int sum = 0;
 5         HashMap<Integer, Integer> map = new HashMap<>();
 6         map.put(0, 1);
 7 
 8         for (int i = 0; i < nums.length; i++) {
 9             sum += nums[i];
10             if (map.containsKey(sum - k)) {
11                 res += map.get(sum - k);
12             }
13             map.put(sum, map.getOrDefault(sum, 0) + 1);
14         }
15         return res;
16     }
17 }

前缀和prefix sum题目总结

LeetCode 题目总结