LeetCodeHot100(10/100)
法一：暴力枚举法
时间复杂度O(n)
class Solution {
public int subarraySum(int[] nums, int k) {
int len = nums.length;
int count = 0;
for (int i = 0; i < len; i++) {
int sum = nums[i];
if (sum == k) {
count++;
}
for (int j = i + 1; j < len; j++) {
sum += nums[j];
if (sum == k) {
count++;
}
}
}
return count;
}
}
法二：前缀和＋哈希表，注意getOrDefault函数的使用
class Solution {
public int subarraySum(int[] nums, int k) {
//前缀和＋哈希表
Map<Integer, Integer> hp = new HashMap<>();
int sum = 0;
int count = 0;
hp.put(0, 1);
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (hp.containsKey(sum - k))
count += hp.get(sum - k);
hp.put(sum, (hp.getOrDefault(sum, 0)) + 1);
}
return count;
}
}