투 포인터(Two Pointers) 알고리즘 완벽 가이드 – 배열 탐색 O(n) 최적화의 정석

배열: [1, 3, 5, 7, 9, 11]
       ↑                 ↑
      left              right

배열: [1, 3, 5, 7, 9, 11]
       ↑  ↑
      left right  → 둘 다 오른쪽으로 이동

def two_sum_sorted(arr, target):
    """
    정렬된 배열에서 합이 target인 두 수의 인덱스를 반환한다.

    시간 복잡도: O(n) - 각 포인터가 최대 n번 이동
    공간 복잡도: O(1) - 포인터 2개만 사용
    """
    left = 0              # 왼쪽 포인터: 배열의 시작
    right = len(arr) - 1  # 오른쪽 포인터: 배열의 끝

    while left < right:
        current_sum = arr[left] + arr[right]

        if current_sum == target:
            # 정답 발견
            return (left, right)
        elif current_sum < target:
            # 합이 부족 → 더 큰 값이 필요 → left를 오른쪽으로
            left += 1
        else:
            # 합이 초과 → 더 작은 값이 필요 → right를 왼쪽으로
            right -= 1

    return None  # 합이 target인 쌍이 없음


# 예제 실행
arr = [1, 3, 5, 7, 9, 11]
target = 12
result = two_sum_sorted(arr, target)
print(f"인덱스: {result}")  # (0, 5) → arr[0]+arr[5] = 1+11 = 12

def min_subarray_length(arr, S):
    """
    합이 S 이상인 가장 짧은 연속 부분 배열의 길이를 반환한다.

    시간 복잡도: O(n) - left와 right 각각 최대 n번 이동
    공간 복잡도: O(1)
    """
    n = len(arr)
    left = 0
    current_sum = 0
    min_length = float('inf')  # 최소 길이를 무한대로 초기화

    for right in range(n):
        # 1단계: 구간 확장 - right가 가리키는 값을 합에 추가
        current_sum += arr[right]

        # 2단계: 구간 축소 - 합이 S 이상인 동안 left를 이동
        while current_sum >= S:
            # 현재 구간의 길이로 최솟값 갱신
            min_length = min(min_length, right - left + 1)
            # left를 오른쪽으로 이동 (구간 축소)
            current_sum -= arr[left]
            left += 1

    # 조건을 만족하는 구간이 없으면 0 반환
    return min_length if min_length != float('inf') else 0


# 예제 실행
arr = [2, 3, 1, 2, 4, 3]
S = 7
result = min_subarray_length(arr, S)
print(f"최소 길이: {result}")  # 2 → [4, 3]

def three_sum(nums):
    """
    합이 0인 세 수의 조합을 모두 반환한다 (중복 없음).

    시간 복잡도: O(n^2) - 외부 루프 O(n) × 내부 투 포인터 O(n)
    공간 복잡도: O(1) - 결과 리스트 제외 (정렬은 in-place)
    """
    nums.sort()  # 정렬: 투 포인터 사용을 위한 전제 조건
    result = []
    n = len(nums)

    for i in range(n - 2):
        # 최적화: 가장 작은 수가 양수면 합이 0이 될 수 없음
        if nums[i] > 0:
            break

        # 중복 건너뛰기: 같은 값의 i는 한 번만 처리
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        # i를 고정하고, 나머지 구간에서 투 포인터 탐색
        left = i + 1
        right = n - 1
        target = -nums[i]  # 나머지 두 수의 합이 -nums[i]여야 함

        while left < right:
            current_sum = nums[left] + nums[right]

            if current_sum == target:
                result.append([nums[i], nums[left], nums[right]])

                # 중복 건너뛰기: left와 right 모두 같은 값은 스킵
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1

                # 양쪽 포인터 모두 이동
                left += 1
                right -= 1
            elif current_sum < target:
                left += 1
            else:
                right -= 1

    return result


# 예제 실행
nums = [-1, 0, 1, 2, -1, -4]
result = three_sum(nums)
print(f"결과: {result}")  # [[-1, -1, 2], [-1, 0, 1]]

def max_area(height):
    """
    가장 많은 물을 담을 수 있는 넓이를 반환한다.

    시간 복잡도: O(n)
    공간 복잡도: O(1)
    """
    left = 0
    right = len(height) - 1
    max_water = 0

    while left < right:
        # 현재 두 벽으로 담을 수 있는 물의 양
        width = right - left
        h = min(height[left], height[right])
        max_water = max(max_water, width * h)

        # 낮은 쪽 벽을 이동 (높은 벽을 만날 가능성을 열어둠)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_water


# 예제 실행
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
print(f"최대 물의 양: {max_area(height)}")  # 49

def opposite_direction(arr, target):
    arr.sort()  # 정렬 필수
    left, right = 0, len(arr) - 1

    while left < right:
        val = arr[left] + arr[right]  # 조건에 맞게 수정

        if val == target:
            # 정답 처리
            return (left, right)
        elif val < target:
            left += 1
        else:
            right -= 1

    return None

def same_direction(arr, condition):
    left = 0
    current = 0  # 윈도우 내 상태 (합, 개수 등)
    answer = float('inf')  # 또는 0 (최대/최소에 따라)

    for right in range(len(arr)):
        # 윈도우 확장
        current += arr[right]  # 조건에 맞게 수정

        # 조건 만족 시 윈도우 축소
        while current >= condition:  # 조건에 맞게 수정
            answer = min(answer, right - left + 1)
            current -= arr[left]
            left += 1

    return answer