HT: Subarray Sum *

👩‍💻 문제

 

몇 번 인덱스에서 몇 번 인덱스까지 더해야 target값이 나오는지, 그 인덱스 쌍을 리스트로 구하는 문제

 

Given an array of integers nums and a target integer target, write a Python function called subarray_sum that finds the indices of a contiguous subarray in nums that add up to the target sum using a hash table (dictionary).

Your function should take two arguments:

nums: a list of integers representing the input array

target: an integer representing the target sum


Your function should return a list of two integers representing the starting and ending indices of the subarray that adds up to the target sum. If there is no such subarray, your function should return an empty list.

For example:
nums = [1, 2, 3, 4, 5]
target = 9
print(subarray_sum(nums, target))  # should print [1, 3]

 

 

 

💡 풀이

def subarray_sum(nums, target):
    num_dict = {0:-1}
    current_sum = 0
    for i, num in enumerate(nums):
        current_sum += num
        if current_sum - target in num_dict:
            return [num_dict[current_sum - target] + 1,i]
        num_dict[current_sum] = i
    return []

 

✍️ 해설

빡센데 ... 

일단 idea는 여기까지 맞았다

타겟값이 10이라고 하면, [1,2,3,4,5] 인 리스트에서 2,3,4를 더해야 10이 나오니까 인덱스는 [1,3]

합으로만 보면 [1,3,6,10,15] 이고 각각의 원소에서 타겟값을 뺀 건 [-9, -6, -3, 1, 5] 이다

 

딕셔너리에 {현재까지의 합 : 인덱스} 를 추가하도록 한다. 그러면

{1:0, 3:1, 6:2, 10:3, 15:4} 이렇게 완성된다

 

현재까지의 합인 current_sum - target값이 이 딕셔너리에 없는 경우,  현재까지의 합 값을 딕셔너리에 하나씩 추가한다

그러다가, current_sum - target값 (1) 이 이 딕셔너리 안에 있는 순간 ! 그 값의 +1 인덱스부터가 시작 인덱스다!

 

 

 

여기서 num_dict = {0 : -1 } 로 놔주는 이유는, 합의 값이 [ 0 , 0 ]. 즉 첫번째 값에서 완성되는 경우 에러를 방지하기 위해서다

 

 

초기화 {0: -1}의 의미
current_sum이 0이 되는 시점을 -1로 초기화합니다.
이는 부분 배열이 첫 번째 요소에서 시작할 때를 처리하기 위함입니다.

부분 배열이 첫 번째 요소에서 시작하는 경우:
예를 들어, nums = [5, 2, -2, 3], target = 5라고 합시다.
첫 번째 반복 (i = 0)에서, current_sum은 5가 됩니다.
current_sum - target는 5 - 5 = 0이 됩니다.
0이 num_dict에 있는 경우, num_dict[0]은 -1이므로, num_dict[0] + 1 = 0이 되어 부분 배열 [0, 0]을 반환합니다.
빈 딕셔너리를 사용할 경우의 문제점

만약 num_dict가 빈 딕셔너리로 초기화되면:
첫 번째 요소에서 시작하는 부분 배열을 찾을 수 없습니다. 즉, current_sum - target이 0이 되더라도, num_dict에 0이 없기 때문에 부분 배열을 찾을 수 없습니다.

 

🥳 배운점

base case 라고 볼 수 있는, 맨 처음 값이 곧 타겟값인 경우를 빼먹지 말고 잘 생각해야겠다