560. Subarray Sum Equals K
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Approach
Có thể sử dụng phương pháp tiếp cận bằng cách sử dụng tiền tố tổng và một hashmap để lưu trữ số lần xuất hiện của mỗi tiền tố tổng
Solution - Brute force
1function subarraySum(nums: number[], k: number): number {
2 let count = 0;
3
4 for(let start = 0; start < nums.length; start++) {
5 let sum = 0;
6 for(let end = start; end < nums.length; end++) {
7 sum += nums[end];
8 if(sum === k) {
9 count++
10 }
11 }
12 }
13 return count;
14}Solution - Prefix sum
1function subarraySum(nums: number[], k: number): number {
2 const prefix_map: Map<number, number> = new Map();
3 prefix_map.set(0, 1);
4 let sum = 0;
5 let count = 0;
6
7 for(const num of nums) {
8 sum += num;
9 const target = sum - k;
10 if(prefix_map.has(target)) {
11 count += prefix_map.get(target)!;
12 }
13
14 prefix_map.set(sum, (prefix_map.get(sum) || 0) + 1);
15 }
16 return count;
17}/* index : 0 1 2 3 4 5 6 7 y y x. => found 2 arrays ending at index 5: [2..5] and [4..5] prefix[sum(a[0..1])] = y, prefix[sum(a[0..3])] = y, prefix[sum(a[0..5])] = x cur sum = x how many #times prev sum = target = y = sum - k x - y = k sum - target = k [target=sum-k] [k] = (cur sum) [0...i]. [i+1..j]. = [0...j] prefix in-between-sum = prefix */
function subarraySum(nums: number[], k: number): number { const prefix_map: Map<number, number> = new Map(); // prefix_map[sum=a[0..]] = freq prefix_map.set(0, 1); let sum = 0; let count = 0; // for every ending point j, find how many starting points i s.t. sum(a[i+1..j]) = k for (const num of nums) { sum += num; const target = sum - k; if (prefix_map.has(target)) { count += prefix_map.get(target)!; // + # valid subarray ending with cur num }
prefix_map.set(sum, (prefix_map.get(sum) || 0) + 1);
}
return count;
}