연속 부분수열 1(투포인터)

5_hyun 2022. 8. 24. 23:58

해결법

이 문제도 투포인터를 사용하면 쉽게 해결된다. lt을 왼쪽, rt를 오른쪽으로 두고 rt를 하나씩 증가 시켜보면서 sum과 같으면 answer을 증가시키면 된다. 만약 rt를 더하다가 m보다 더 커지면 lt에 있는 값을 빼고 lt 인덱스를 1 증가 시킨다. 이때 sum이 m과 같은지 확인하면 된다.

코드

<html>
  <head>
    <meta charset="UTF-8" />
    <title>출력결과</title>
  </head>
  <body>
    <script>
      function solution(m, arr) {
        let answer = 0,
          lt = 0,
          sum = 0;

        for (let rt = 0; rt < arr.length; rt++) {
          sum += arr[rt];

          if (sum === m) answer++;
          while (sum >= m) {
            sum -= arr[lt++];
            if (sum === m) answer++;
          }
        }

        return answer;
      }

      let a = [1, 2, 1, 3, 1, 1, 1, 2];
      console.log(solution(6, a));
    </script>
  </body>
</html>

저작자표시 (새창열림)