LV 2: 연속된 부분 수열의 합

문제 링크

LV 2: 연속된 부분 수열의 합

구현 방식

• 투 포인터 알고리즘을 적용하여 풀었다
  • 1) start와 end가 0을 가리키도록 한다
  • 2) part_sum이 k보다 작다면 end를 1 증가시킨다
  • 3) part_sum이 k와 같다면, result에 수열의 길이와 start, end를 추가해준다
  • 4) part_sum이 k보다 크거나 같다면, start를 1 증가시킨다
  • 2) ~ 4)를 모든 경우를 돌때까지 반복한다

코드

def solution(sequence, k):
    
    N = len(sequence)
    part_sum = 0
    end = 0
    
    result = []
    for start in range(N):
        
        while part_sum < k and end < N: # end를 가능한만큼 이동
            part_sum += sequence[end]
            end += 1
        
        if part_sum == k:
            result.append((end - start, start, end-1))
        part_sum -= sequence[start]
    
    result.sort()
    return [result[0][1], result[0][2]]