本文主要是介绍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思路：用prefixsum prefixsum[j+1] - prefixsum[i] = k, 类似2sum，用hashmap优化，注意先判断是否含有，再加入，否则会有重复计算；if(sum == k) count++;
class Solution {public int subarraySum(int[] nums, int k) {if(nums == null || nums.length == 0) {return 0;}int n = nums.length;int[] prefixSum = new int[n + 1];for(int i = 1; i <= n; i++) {prefixSum[i] = prefixSum[i - 1] + nums[i - 1];}HashMap<Integer, Integer> hashmap = new HashMap<>();// sum frequency;int count = 0;for(int i = 1; i <= n; i++) {if(prefixSum[i] == k) {count++;}// 存prefixsum -k, 也就是之前的比较小的数，这样在后面一旦碰见，那么就表示相吻合，a - b = k;if(hashmap.containsKey(prefixSum[i] - k)) {count += hashmap.get(prefixSum[i] - k);}hashmap.put(prefixSum[i], hashmap.getOrDefault(prefixSum[i], 0) + 1);}return count;}
}减少内存，可以用cursum来代替prefixsum；
class Solution {public int subarraySum(int[] nums, int k) {if(nums == null || nums.length == 0) {return 0;}int n = nums.length;int cursum = 0;// sum frequency;HashMap<Integer, Integer> hashmap = new HashMap<>();int count = 0;for(int i = 0; i < nums.length; i++) {cursum += nums[i];if(cursum == k) {count++;}// 存prefixsum - k, 也就是之前的比较小的数，这样在后面一旦碰见，那么就表示相吻合，a - b = k;// count已经加过1了，那么这里只需要加入之前的频率。if(hashmap.containsKey(cursum - k)) {count += hashmap.get(cursum - k);}// hashmap里面的频率要+1；hashmap.put(cursum, hashmap.getOrDefault(cursum, 0) + 1);}return count;}
}这篇关于Subarray Sum Equals K的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
