Description
Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,1,1], k = 2
Output: 2
Example 2:
Input: nums = [1,2,3], k = 3
Output: 2
Constraints:
1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107
Solutions
Solution 1: Hash Table + Prefix Sum
We define a hash table cnt to store the number of times the prefix sum of the array nums appears. Initially, we set the value of cnt[0] to 1, indicating that the prefix sum 0 appears once.
We traverse the array nums, calculate the prefix sum s, then add the value of cnt[s - k] to the answer, and increase the value of cnt[s] by 1.
After the traversal, we return the answer.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array nums.
PythonJavaC++GoTypeScriptRust
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
cnt = Counter({0: 1})
ans = s = 0
for x in nums:
s += x
ans += cnt[s - k]
cnt[s] += 1
return ans(code-box)
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> cnt = new HashMap<>();
cnt.put(0, 1);
int ans = 0, s = 0;
for (int x : nums) {
s += x;
ans += cnt.getOrDefault(s - k, 0);
cnt.merge(s, 1, Integer::sum);
}
return ans;
}
}(code-box)
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> cnt{{0, 1}};
int ans = 0, s = 0;
for (int x : nums) {
s += x;
ans += cnt[s - k];
++cnt[s];
}
return ans;
}
};(code-box)
func subarraySum(nums []int, k int) (ans int) {
cnt := map[int]int{0: 1}
s := 0
for _, x := range nums {
s += x
ans += cnt[s-k]
cnt[s]++
}
return
}(code-box)
function subarraySum(nums: number[], k: number): number {
const cnt: Map<number, number> = new Map();
cnt.set(0, 1);
let [ans, s] = [0, 0];
for (const x of nums) {
s += x;
ans += cnt.get(s - k) || 0;
cnt.set(s, (cnt.get(s) || 0) + 1);
}
return ans;
}(code-box)
use std::collections::HashMap;
impl Solution {
pub fn subarray_sum(nums: Vec<i32>, k: i32) -> i32 {
let mut cnt = HashMap::new();
cnt.insert(0, 1);
let mut ans = 0;
let mut s = 0;
for &x in &nums {
s += x;
if let Some(&v) = cnt.get(&(s - k)) {
ans += v;
}
*cnt.entry(s).or_insert(0) += 1;
}
ans
}
}(code-box)
