leetcode 560) Subarray Sum Equals K

LV. Medium 🧐

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

Subarray Sum Equals K - LeetCode

 

문제

Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

 

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 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7

 

문제 해결법

배열을 처음부터 끝까지 돌면서 sum 값을 저장해준다.

또한 sum이 나오는 개수도 맵에 저장해준다. 

n번째 인덱스에서의 sum - k의 값이 7일 때 맵의 7 키에 2가 저장되어 있으면, n번째 인덱스에서 배열 앞쪽으로 찾을 수 있는 조합의 개수가 2개인 것이다.

 

sum - k의 값이 맵에 있으면 count에 저장!

마지막에 count를 리턴하면 끝!

 

해결 코드

class Solution {
private:
	unordered_map<int, int> m;
	int count;
	int sum;

public:
	int subarraySum(vector<int>& nums, int k) {
		count = 0;
		sum = 0;

		m[0] = 1;
		for (int i = 0; i < nums.size(); ++i) {
			sum += nums[i];
			if (m.find(sum - k) != m.end())
				count += m[sum - k];
			if (m.find(sum) == m.end())
				m[sum] = 1;
			else
				m[sum]++;
		}
		return count;
	}
};