[leetcode 560] 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

 

Constraints:

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

 

풀이:

처음 접근한 방법은 투포인터...하지만 투포인터가 작동하려면 배열 안의 수가 전부 양수라는 조건이 있어야 한다.

-> leetcode.com/problems/subarray-sum-equals-k/discuss/301242/General-summary-of-what-kind-of-problem-can-cannot-solved-by-Two-Pointers

 

대신 사용해야 하는 방법은 누적합과 매핑

- 매번 누적합을 계산한다. 

- 만약 현재의 누적합이 목적 값k를 초과한다면 맵에서 누적합-목적값k를 한 값이 있는 지 확인한다.

-> 있다면 결과값에 더해준다.

- map의 사용: map.find(key)는 key에 해당하는 값이 없을 경우 map.end()를 return

-> if (map.find(key) != map.end()) 는 key값이 map에 존재하는지 여부를 확인하는 것.

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        
        map<int, int>dp; //누적합을 저장하는 매핑
        int sum = 0, res=0;
        for(int i=0; i<nums.size(); i++){
            sum += nums[i];
            if(sum == k){
                res++;
            }
            
            if(dp.find(sum-k) != dp.end()){
                res += dp[sum-k];
            }
            
            dp[sum]++;
        }
        
    return res;
        
    }
};