1248. Count Number of Nice Subarrays

문제

https://leetcode.com/problems/count-number-of-nice-subarrays/description/

풀이

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);

        int answer = 0;
        int curr = 0;

        for(int n : nums) {
            curr += n % 2;
            answer += map.getOrDefault(curr - k, 0);
            map.put(curr, map.getOrDefault(curr, 0) + 1);
        }

        return answer;
    }
}

• subarray 탐색? lt를 이동시킬 때, rt++의 값이 짝수인지 홀수인지 비교해야하고, lt의 값도 짝수인지 홀수인지 비교해야하고.. 너무 복잡함 -> sliding window 대신 누적합 + HashMap 카운팅 사용
• 현재 인덱스까지의 홀수 개수를 세어서 저장, 동일 개수의 경우 카운팅해서 ++
  • 현재 인덱스 i에서의 홀수 k개를 만족하는 부분 배열은 curr - k을 만족하는 배열부터 시작하여 k까지의 배열 (사이에는 홀수가 k개 있기 때문)
• 홀수 개수가 0개인 경우도 처음에 초기화 해줘야, curr = k일 때 값을 구할 수 있다.