https://leetcode.com/problems/subarray-sum-equals-k/

Input: nums = [1,1,1], k = 2
Output: 2

Input: nums = [1,2,3], k = 3
Output: 2

연속된 subarray들 중 합이 k인 경우의 수를 모두 찾아서 return 해준다.

cumulative(누적) sum different 개념을 활용한다.

cumulatuive sum diff가 무엇인가...

[ 6 3 2 5 3 -3 ] 에서 sum 10이 되는 sub array를 찾으라 해보자.

[6 9 11 16 19 16] 과 같이 더해간다.

해당 결과물을 hash map을 통해서 key값으로 값을 넣고, val값으로 index를 넣어준다.

그리고 두 값의 차이가 10이 되는 곳이 10되는 sub array이 일 것이다.

19 와 9 / 16 과 6 (2가지가 있다.)

시작 부분이 6, 끝 부분이 16이면, idx[3] - idx[0] 이 될 것이다. 따라서 [3, 2, 5] 가 된다.

그리고 edge case를 생각해야 하는데 [6, 3, 2] 도 10이 된다. 그렇기 때문에 처음 시작 부분이 될 edge case를 넣어줘야 한다. index -1 과 val 0을 넣어준다. hash map 에도 넣어준다.

class Solution {
public:
	int subarraySum(vector<int>& nums, int k) {
		std::unordered_map<int, int> umap;
		umap[0] = 1; // edge case를 위해

		int sum = 0;
		int total = 0;
		
		for (int i = 0; i < nums.size(); ++i)
		{
			sum += nums[i];

			if (umap.find(sum - k) != umap.end()) // 2를 찾는다 하면 1 - 2 = -1. 없으니까 패스 (보기 1)
				total += umap[sum - k];

			if (umap.find(sum) != umap.end())
				umap[sum]++;
			else
				umap[sum] = 1;
		}

		return total;
	}
};

Runtime: 68 ms, faster than 94.87% of C++ online submissions for Subarray Sum Equals K.

Memory Usage: 36 MB, less than 97.06% of C++ online submissions for Subarray Sum Equals K.