[인프런 섹션5] 연속 부분수열 2 (Javascript)

👩🏻‍💻문제링크

[인프런 섹션5] 연속 부분수열 2 (Javascript)
유료 강의인 관계로 문제 설명은 생략합니다.

✍️Idea Sketch

2021-06-25

1. left부터 right까지의 합이 m보다 작거나 같으면

1) cnt += (left부터 right까지 원소의 개수)

cnt += right - left + 1

2) right++

2. left부터 right까지의 합이 m보다 크면 left++

3. Example

1) left가 0, right가 2일 때 --> 원소는 1, 3, 1 --> sum === m (5 === 5)

• 연속부분수열 {1, 3, 1}, {3, 1}, {1} 총 3개가 추가됨

2) left가 0, right가 3일 때 --> 원소는 1, 3, 1, 2 ==> sum > m (7 > 5)
3) left가 1, right가 3일 때 --> 원소는 3, 1, 2 ==> sum > m (6 > 5)
4) left가 2, right가 3일 때 --> 원소는 1, 2 ==> sum < m (3 < 5)

• 연속부분수열 {1, 2}, {2} 총 2개가 추가됨

✍️소스코드

2021-06-25

function solution(arr, m) {
  let left = 0, right = 0;
  let sum = arr[0];
  let cnt = 0;

  while (left<arr.length && right<arr.length) {
    if (sum <= m) {
      cnt += right - left + 1;
      sum += arr[++right];
    }
    else if (sum > m) sum -= arr[left++];
  }

  return cnt;
}