30daychallenge (22) | 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:

1. The length of the array is in range [1, 20,000].
2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

Không biết ngày xưa nghĩ thế nào, nhưng giờ mình viết bài này chưa tới 5 dòng ..

Với [1,1,1] cộng cuốn chiếu được sum = [1,2,3], trên mảng sum, giống như đề bài cũ tôi làm tìm đoạn dài nhất 0,1. Ta thêm 0 [1,2,3] . Nếu sum-k tồn tại trong map, biến res = res + map(sum-k).
Nếu sum = 1,2,3 đã tồn tại trong map, ta sẽ cộng sum thêm 1. Ví dụ [0,0,0] với tổng bằng 0, thì ta có bảng map (0,1), res = 1 rồi (0,2), res = 3 rồi (0,3), res = 6.

	// duynotes.blogspot.com
	class Solution {
	public int subarraySum(int[] nums, int k) {
	HashMap<Integer,Integer> hm = new HashMap<>();
	int res = 0;
	int sum = 0;
	hm.put(0,1);
	for (int i:nums){
	sum+=i;
	res+=hm.getOrDefault(sum-k,0);
	hm.put(sum,hm.getOrDefault(sum,0)+1);
	}
	return res;
	}
	}

view raw SubArraySumEqualK.java delivered with ❤ by emgithub

Cảm ơn bạn !