Target Sum

You are given a list of n integers and an arbitrary integer target value target. Your task involves finding a pair of integers in the array whose sum equals the value of target. If multiple pairs satisfy this condition, choose the one with a lower index of the last element that appears in the array. If no pairs' sum equals target, return an empty list.

Constraints:

• 1≤n≤10000001≤n≤1000000
• −1000000≤arr[i]≤1000000−1000000≤arr[i]≤1000000
• −2000000≤target≤2000000−2000000≤target≤2000000
• The program should work within 3 seconds.

Example:

For the input array arr = [2, 13, 4, 7, 5, 15] and a target target = 9, the output should be [2, 7] because the sum of these numbers equals 9. [4, 5] is also a valid pair, but it appears later.

 

def solution(arr, target):
    # TODO: implement a function that finds a pair of numbers whose sum equals the target
    res = []    
    num2idx = {}
    best_last_idx = float("inf")
    
    for i, num in enumerate(arr):
        remain = target-num
        if remain in num2idx: # dic 에 있으니, remain 이 index 가 앞선 값
            j = num2idx[remain]
            # 마지막 인덱스가 더 작으면 갱신
            if max(i, j) < best_last_idx:
                best_last_idx = max(i, j)
                res = [remain, num]
                
        if num not in num2idx:
            num2idx[num] = i
    return res