01. two pointers.md

Two Pointers Algorithm;투 포인터 알고리즘

• 슬라이딩 윈도우 알고리즘은 범위가 고정되어 있지만, 투 포인터 알고리즘은 범위가 동적으로 변한다.
• 이중반복문의 시간복잡도는 O(n^2) 이므로 배열 크기가 커질수록 연산량이 제곱으로 증가하는 반면,
  투 포인터 알고리즘의 시간복잡도는 O(n) 이므로 더 효율적이다.
• 요소의 합계나 평균이 k 인 연속부분수열을 모두 찾을 때

배열의 처음에서 시작하여 마지막으로 이동하는 경우

1. 필요 시 배열 정렬
2. 두 포인터 모두 0 번째로 초기화
3. 계산한 값이 k 보다 작다면 끝 포인터를 오른쪽으로 이동
4. 계산한 값이 k 보다 크다면 시작 포인터를 오른쪽으로 이동

// section5 3번 문제
const solution = (m, arr) => {
  let answer = 0,
    sum = 0;
  let lt = 0;

  for (let rt = 0; rt < arr.length; rt++) {
    // sum 이 m 보다 작다면
    // 끝 포인터를 오른쪽으로 이동
    // 그리고 끝 포인터 값을 sum 에 합산
    sum += arr[rt];
    if (sum === m) answer++;
    while (sum >= m) {
      // sum 이 m 보다 크거나 같다면
      // 시작 포인터 값을 sum 에서 뺀 후
      // 시작 포인터를 오른쪽으로 이동
      sum -= arr[lt++];
      if (sum === m) answer++;
    }
  }
  return answer;
};

let a = [1, 2, 1, 3, 1, 1, 1, 2];
console.log(solution(6, a));

// 1 ~ n 중에서 합계가 n 인 연속부분수열의 개수를 출력
// while 문 사용
const solution = (n) => {
  let answer = 0;
  let sum = 0;
  let lt = 1;
  let rt = 1;

  while (rt <= n) {
    sum += rt++;
    while (sum > n) {
      sum -= lt++;
    }
    if (sum === n) answer++;
  }
  return answer;
};

배열의 양 끝에서 시작하여 가운데로 이동하는 경우

1. 필요 시 배열 정렬
2. 시작 포인터와 끝 포인터를 각각 0 과 배열 크기 - 1 번째로 초기화
3. 계산한 값이 k 보다 작다면 시작 포인터를 오른쪽으로 이동
4. 계산한 값이 k 보다 크다면 끝 포인터를 왼쪽으로 이동

const solution = (m, arr) => {
  let answer = [];
  let p1 = 0;
  let p2 = arr.length - 1;

  arr.sort((a, b) => a - b);
  while (p1 < p2) {
    const sum = arr[p1] + arr[p2];
    if (sum < m) p1++;
    if (sum > m) p2--;
    else {
      answer.push([arr[p1], arr[p2]]);
      p1++;
      p2--;
    }
  }
  return answer;
};

let a = [1, 2, 5, 8, 3, 4, 6];
console.log(solution(6, a));