k개 홀수가 있는 연속부분수열의 집합

이 문제는 숫자들 중, k개의 홀수가 있는 연속 부분 수열 집합의 수를 구하는 문제입니다. 이 문제는 투포인터 와 해쉬 를 이용해 풀 수 있습니다.

function solution(nums, k) {
  function countOdd(k) {
    let left = 0,
      odd = 0,
      sum = 0;
    for (let right = 0; right < nums.length; right++) {
      if (nums[right] % 2 === 1) odd++;

      while (odd > k) {
        if (nums[left] % 2 === 1) odd--;
        left++;
      }
      sum += right - left + 1;
    }
    return sum;
  }
  return countOdd(k) - countOdd(k - 1);
}

투포인터

1. 홀수의 갯수가 0~k개를 넘기지 않는 모든 연속 부분 수열 집합의 수를 반환하는 countOdd 함수를 만듭니다.
2. right 인덱스를 이동시키며 홀수가 있으면 odd 를 1씩 증가합니다.
3. odd 가 k 보다 커지면 odd가 k보다 크지 않을 때까지 odd 를 1씩 감소시키고, left 인덱스를 증가시킵니다.
4. sum 에는 left와 right 인덱스 사이의 연속 부분 수열 집합의 수를 계속해서 더합니다.
5. countOdd(k) 는 0~k 개를 넘기지 않는 모든 연속 부분 수열 집합의 수이고, countOdd(k-1)은 0~k-1 개를 넘기지 않는 모든 연속 부분 수열 집합의 수입니다. 그러므로 countOdd(k) - countOdd(k-1)은 k 개를 넘기지 않는 모든 연속 부분 수열 집합의 수만 남습니다.

function solution(nums, k) {
  let count = 0;
  let odd = 0;
  let hash = new Map();

  for (let num of nums) {
    if (num % 2 === 1) odd++;
    if (odd === k) count++;

    if (hash.has(odd - k)) count += hash.get(odd - k);
    hash.set(odd, (hash.get(odd) || 0) + 1);
  }
  return count;
}

해쉬

1. 배열을 순회하며 숫자가 홀수면 odd 를 1씩 증가시킵니다.
2. odd가 k 와 값이 같아지면 count를 1씩 증가시킵니다.
3. map 자료형인 hash 변수에 odd-k 의 값이 있으면, 홀수를 k 개 포함시킨 연속 부분 수열 집합의 수가 그 값만큼 있는 것이므로 count 를 값만큼 증가시킵니다.
4. odd의 값은 hash 의 키로 하고, 값을 1씩 증가시킵니다.
5. 순회가 끝나면 count 를 return 합니다.