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
Note:
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的子数组
思路：
1. The key to solve this problem is to find subarray sum[i, j] == k
2. if we know sum[0, i-1], sum[0,j] we can check sum[0, i-1] - k == sum[0,j] ?
3. To achieve this, we traversal whole array, save sum[0,j] as preSum in map, checking curSum[0,i-1] - k is contained in map
nums = [5, 2, 3, 4, 5] k= 7
sum=5
=7
=10
=14
map
sum frequency check (sum - k) in map?
init 0 1
5 1 5-7=-2 No
7 1 7-7=0 Yes update res
10 1 10-7=3 No
14 1 14-7=7 Yes update res
代码：
1 public class Solution { 2 public int subarraySum(int[] nums, int k) { 3 int sum = 0, result = 0; 4 Map<Integer, Integer> map = new HashMap<>(); 5 map.put(0, 1); 6 7 for (int i = 0; i < nums.length; i++) { 8 sum += nums[i]; 9 if (map.containsKey(sum - k)) { 10 result += map.get(sum - k); 11 } 12 map.put(sum, map.getOrDefault(sum, 0) + 1); 13 } 14 15 return result; 16 } 17 }
转载于:https://www.cnblogs.com/liuliu5151/p/9810120.html
