https://leetcode.com/problems/subarray-sum-equals-k/
합이 k 가 되는 subarray 의 개수를 구하기
naive 한 풀이
contiguous element 들로 이루어져 있는 것을 구하기 때문에
연속한 원소들로 이루어진 subarray 이니
i~ j 까지의 모든 경우들을 해 보면 되지 않을까 ? 라는 생각을 했음.
그런데 이렇게 할 경우, 20000, 19999, ... 1 가지의 경우가 나오고 총 합은 억대임
그래도 naive 한 풀이를 해 봐야 subproblem 을 도출 할 수 있을 듯.
그리고 심지어 naive 한 것도 제대로 생각 모함
- 정렬되어 있는 배열이 아니다
- 0 이 존재한다 -> 0 을 포함시킬 수 있다.
- 뒤에 음수가 나오면, 현재까지 sum > k 이었더라도, sum == k 가 될 수도 있다.
누적합
한 번 nums 를 모두 돌아서(traverse) --> sum array 를 채운다.
그러고 나면 i ~ j 까지의 sum 은, 이제 nums[i] + nums[i+1] + ... + nums[j] 를 하지 않고, sum[j] - sum[i] 만으로도 구할 수 있게 된다. 물론 모든 i, j 조합을 해 봐야 하긴 하지만. -> O(n^2)
모든 i, j 조합 x (누적을 위한 j-i) 를 하는 것보다는 나을 것.
이라 생각했는데 시간은 더 최악이었음;; ㅠㅠ 근데 일단 LeetCode 에서는 naive 하게 푸는거나 누적합으로 푸는 거나 시간초과로 fail 시키지는 않고 있었다.
// accumulated sum
private int accum(int[] nums, int k) {
// to make sum, time complexity O(n) - sum[i + 1 ] = sum[i] + nums[i + 1] -> to make it easier, init sum[0] = 0,and make sum array as array which size is nums.length + 1
int cnt = 0;
int[] sum = new int[nums.length + 1];
sum[0] = 0;
for(int i = 0; i < nums.length; i++) sum[i + 1] = sum[i] + nums[i];
// sum of (i, j) -> sum[j] - sum[i] -> 모든 조합 만드려면 O(n^2)
for(int i = 0; i < nums.length; i++) {
for(int j = i + 1; j <= nums.length; j++) {
if(sum[j] - sum[i] == k) cnt++;
}
}
return cnt;
}hashmap ?
보니까 다른 사람들은 이 문제를 hashmap 을 사용해서 최적화를 하였다.
contiguous 해야하는 것이기 때문에, map 을 사용하면 안 되는 거 아닌가?? 라는 생각이 들었다.
뭐 어떻게 푼다는거지? 사실 나는 이것 조차도 이해가 잘 안되었닿..ㅎ 알고리즘은 나한테 큰 벽인 것 같다
두 번째 방식은 모든, 생성할 수 있는 i,j 조합에 대해
sum[j] - sum[i] 가 k 인지를 확인하는 방식이었다.
j 는 nested loop 상에서 사용하는 컨트롤 변수였다.( 따라서 항상 i < j 이다 -> 좀 더 이해하기 쉽게 하려면 start, end 관계로 생각하는 것이 좋을 것 같다)
즉 조건문에서는 이를 확인하는 것이었다.
sum[end] - sum[start] == k
위 사실을 활용하는 것이다!
어떤 end 와 매칭되는 start 들을 찾는 다는 것은
sum[end] - k = sum[start] 인 모든 start 들을 찾는 것과 같다.
만약 sum 배열을 첫 번째 index 부터 순차적으로 접근 하면서, sum[idx] 를 map 에 {sum[idx] : 이 sum[idx] 가 등장한 횟수} 로 저장한다면,
map 에는 sum[end] - k = sum[start] 인 start 들이 저장되어 있을 것이다.
근데 여기서 map.put(0,1) 을 해 두지 않으면 왜 안될까???
sum[end] - k == 0 인 경우에도 카운트를 1 해야 하는데,이렇게 해 두지 않으면 1 이 증가하지 않는다.
