[LeetCode] 560. Subarray Sum Equals K - 문제풀이

Description

주어진 배열에서 연속된 부분배열의 합이 k가 되는 모든 케이스를 반환하는 문제입니다.

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

Accepted

694.2K

Solution 1. prefix sum

public int subarraySum(int[] nums, int k) {
        
    // 1. dp
    int len = nums.length;
    int cnt = 0;

    int[] dp = new int[len+1];
    for (int i = 0; i < len; i++) { // dp[i]는 현재 인덱스 전(i-1)까지의 누적합
        dp[i+1] = dp[i]+nums[i];
    }
    for (int i = 0; i < dp.length; i++) {
        for (int j = i+1; j < dp.length; j++) {
            if(dp[j]-dp[i] == k){
                cnt++;
            }
        }
    }
    return cnt;

}

dynamic progamming을 이용해 각 인덱스 별로 누적합을 미리 계산한 뒤 모든 subarray의 합을 체크하여 카운팅합니다.

Solution 2. prefix sum + HashTable

public int subarraySum2(int[] nums, int k) {
        
	int len = nums.length;
	int cnt = 0;
	int sum = 0;
	HashMap<Integer, Integer> map = new HashMap <>();
	map.put(0, 1);
		
	for (int i = 0; i < len; i++) {
		 sum += nums[i];
		 if (map.containsKey(sum - k)) {
		     cnt += map.get(sum - k);
		 }
		 map.put(sum, map.getOrDefault(sum, 0) + 1);
	}
	return cnt;

}

먼저 동일하게 각 요소별 합계를 hashmap에 넣어줍니다.

이전의 dp[end] - dp[start] == k 의 조건을 생각해 보면 dp[end]-k == dp[start] 이고 이미 dp[start]의 요소의 개수는 map에 들어 있기 때문에 해당 횟수를 카운팅 해줍니다.

Reference

Subarray Sum Equals K - LeetCode

 

LeetCode, Algorithm, String, Hash Table, LinkedList, Depth-First Search, Breadth-First Search, Matrix, TwoPoint, Array, Recusion, 릿코드, 알고리즘, 코딩테스트, 코테, 문제풀이

Binary Tree, Recusion, 전위순회, inorder-traversal

중위순회, inorder-traversal, 후위순회, postorder-traversal,