Leetcode in Java - 560. Subarray Sum Equals K

Brute Force 풀이법

Brute Force 방식으로 nums의 각 원소를 시작점으로 해서, 중첩된 loop를 돌면서 j까지 더했을 때 k가 되는 subarray가 없는지 확인해볼 수 있다. 이때 중첩된 반복문 때문에 시간복잡도는 O(n)이고, 별도의 공간을 사용하고 있지 않기 때문에 공간복잡도는 O(1)이다.

 

// T.C O(n^2)
// S.C O(1) 별도의 공간을 사용하지 않음
class SolutionBruteForce {
        public int subarraySum(int[] nums, int k) {
            int n = nums.length;
            int count = 0;
            for (int i=0; i<n; i++) {
                int j = i;
                int curr = nums[j];
                int sum = 0;
                while (j<n) {
                    sum += nums[j];
                    if (sum == k) count++;
                    j++;
                }
            }
            return count;
        }
    }

 

 

최적화 힌트

1. prefix sum (pre[])을 활용한다.

2. pre[j] - pre[i]는 nums[i] + nums[i+1] + ... + nums[j]를 뜻한다. 

 

 

prefix sum이란

누적합을 말한다. 즉, int[] nums에 대해서 누적합 int[] pre는 다음을 만족한다.

pre[i] = nums[0] + nums[1] + ... + nums[i]
pre[] = [nums[0], nums[0] + nums[1] , ... , nums[0] + ... + nums[i]];

 

 

2번 힌트에 대해서

2번 힌트에서 누적합 원소 간의 차가 바로 우리가 구하고자 하는 `continuous subarray`의 집합임을 알 수 있다.

pre[j] - pre[i] = sum(from i+1 to j) // continuous subarray

 

 

최적화 풀이
we can check if there is a set of pre[i] and pre[j] whose gap is the same as k.
also if pre[i] == k than count ++;
 
 while we can create pre[] first and then
 iterate through to look for conditions,
 we can do it in one loop.
 
 1. fill up the pre[]
 2. check if `prefix-sum == k` then count++;
 3. check if there is sum-k also exists among pre[].

with no.3 we can see map can be efficient sinch it finds a key in O(1) time.
so we will make pre[] as a map instead of array.

 

and we know that since there can be negative elements in given nums, there can be the same prefixsum multiple times. so we keep track of how many prefix-sum happens along and count it into the answer.

for example, our pre[] can look like this [7, 10, 8, 10, 13] and if k is 3, then when we encounter 13 as our current prefix-sum, we should know that there are 2 number of subarrays that meets the condition where pre[j] - pre[i] == k. which is with first 10 and with second 10.

so while we build our prefix-sum as hasmap, the key should be the prefix-sum and value the count of the prefix-sum happens. it looks like this `Map<prefix-sum, count of prefix-sum>`

and whenever we count up the subarrays, we add on our value.

 

 

O(n) 풀이 코드

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int n = nums.length;
        int sum = 0;
        int count = 0;
        for (int i=0; i<n; i++) {
            sum += nums[i];
            if (sum==k) count++;
            if (map.containsKey(sum-k))
                count += map.get(sum-k);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}