[이코테] [7] 투포인터

투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때

두 개의 점의 위치를 기록하면서 처리하는 알고리즘.

 

[ 문제 ]

특정한 합을 가지는 부분 연속 수열 찾기 

- N개의 자연수로 구성된 수열 : [1, 2, 3, 2, 5]

- 합이 M인 부분 연속 수열의 개수를 구하세요.

- 수행 시간 제한은 O(N)입니다.

 

[ 풀이 ]

1) left와 right 두 개의 포인터 사용:

• left: 부분 수열의 시작 인덱스.
• right: 부분 수열의 끝 인덱스 (확장하면서 합을 계산).

2) 슬라이딩 윈도우 방식으로 합을 조절:

• 합(current_sum)이 M보다 작으면 right 증가 (부분 수열 확장).
• 합이 M보다 크면 left 증가 (부분 수열 축소).
• 합이 M이면 카운트 증가하고 left 이동.

3) 모든 요소를 한 번씩만 탐색하므로 O(N)에 해결 가능.

 

설명 1)

설명 2)

설명 3)

설명 4)

설명 5)

설명 6)

설명 7)

 

[ 코드 ]

def count_subarrays_with_sum(nums, M):
    left, right = 0, 0
    current_sum = 0
    count = 0
    n = len(nums)

    while right < n:
        current_sum += nums[right]  # 오른쪽 값 추가
        
        # 합이 M을 초과하면 left를 증가하며 조정
        while current_sum > M and left <= right:
            current_sum -= nums[left]
            left += 1
        
        # 합이 정확히 M이면 카운트 증가
        if current_sum == M:
            count += 1

        right += 1  # 오른쪽 포인터 이동

    return count