투 포인터

[devLupin]

• 배열에서 연속된 부분 배열의 합이 M이 되는 경우의 수를 구할 수 있다.
• 가장 쉬운 방법은 $O(N^2)$이지만, 투 포인터 알고리즘을 이용하면 $O(N)$에 해결 가능하다.
• 주된 문제 유형
  • 연속된 수들의 합
  • 부분 배열의 합
  • 부분 수열의 개수

[devLupin]

부분합이 M이 되는 경우의 수

• 포인터 2개를 같은 방향으로 진행해 나아가는 것
• 방법
  • 2개의 포인터 준비 (start, end)
  • while (start <= end)
  • 현재 부분합이 M 이상이면 start++
  • M 미만이면 end++
  • M과 같으면 경우의 수 ++

[devLupin]

합이 0에 가장 가까운 두 수 구하기

• 배열 오름차순 정렬
• 초기화 : left=0, right=n-1
• left+right > 0 인 경우 합이 더 작아져야 하므로 right--
• left+right <= 0인 경우 합이 더 커져야 하므로 left++