문제)제시된 합을 가진 부분 배열 찾기
- 방법1. 중첩 반복문을 사용 O(n^2)
def find_subarray_with_sum(arr, s):
n = len(arr)
for i in range(n):
current_sum = 0
for j in range(i, n):
current_sum += arr[j]
if current_sum == s:
return [i + 1, j + 1] # 인덱스 기준이 1이므로 +1을 해줌
return -1
print(find_subarray_with_sum([1, 2, 3, 7, 5], 12)) # 출력: [2, 4]
print(find_subarray_with_sum([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 15)) # 출력: [1, 5]- 방법2. 두 개의 포인터를 사용 O(n)
def find_subarray_with_sum(arr, s):
left = right = 0
current_sum = 0
while right < len(arr):
current_sum += arr[right]
while current_sum > s and left < right:
current_sum -= arr[left]
left += 1
if current_sum == s:
return [left + 1, right + 1]
right += 1
return [-1]
print(find_subarray_with_sum([1, 2, 3, 7, 5], 12)) # 출력: [2, 4]
print(find_subarray_with_sum([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 15)) # 출력: [1, 5]
(파이썬에서는 배열의 개념을 리스트로 대신한다..)
