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].
subarray sum 问题常用hashmap, 存count 值和坐标, 动归的感觉啊
public int subarraySum(int[] nums, int k) {
int sum = 0, result = 0;
Map<Integer, Integer> preSum = new HashMap<>();
preSum.put(0, 1);
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (preSum.containsKey(sum - k)) {
result += preSum.get(sum - k);
}
// 当加着加着出现两个一样的sum时, 要在他的value上加1, 因为可以有多个连续的串
preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
}
return result;
}
要用 preSum.put(0, 1); 是得result 加的值可以来自map中的多个.
不能 if (sum == k) {
result++;
}
因为:
public boolean checkSubarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>(){{put(0,-1);}};;
int runningSum = 0;
for (int i=0;i<nums.length;i++) {
runningSum += nums[i];
if (k != 0) runningSum %= k;
Integer prev = map.get(runningSum);
if (prev != null) {
if (i - prev > 1) return true;
}
else map.put(runningSum, i);
}
return false;
}
原文：http://www.cnblogs.com/apanda009/p/7282555.html