首页 > 代码库 > 560. Subarray Sum Equals K
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 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++;
}
因为:
Input:[0,0,0,0,0,0,0,0,0,0] 0
Output:10
Expected:55
对比523. Continuous Subarray Sum, 0 的indice放-1, 0的count 放1;
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;
}
560. Subarray Sum Equals K
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。