560. Subarray Sum Equals K
最容易想到的是暴力法,依次算出每个连续子数组的和,与k比较:
class Solution {
public int subarraySum(int[] nums, int k) {
int count=0;
for(int i=0;i<nums.length;i++){
int sum=0;
for(int j=i;j<nums.length;j++){
sum=sum+nums[j];
if(sum==k)
count++;
}
}
return count;
}
}
此外,我们换种思路,记sum[i]为num[0]~num[i]的和,则sum[i]-sum[j]为num[j+1]~num[i]之间的元素之和。定义一个hashmap,存储sum[i]出现过的次数,如果map[sum[i]-k]存在,则从它对应的下标开始到i之间的元素之和为k。
public class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0, sum = 0;
HashMap < Integer, Integer > map = new HashMap < > ();
map.put(0, 1);
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (map.containsKey(sum - k))
count += map.get(sum - k);
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;
}
}