InterviewBit – 2 Sum

Source: 2 Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 < index2. Please note that your returned answers (both index1 and index2 ) are not zero-based.
Put both these numbers in order in an array and return the array from your function ( Looking at the function signature will make things clearer ). Note that, if no pair exists, return empty list.

If multiple solutions exist, output the one where index2 is minimum. If there are multiple solutions with the minimum index2, choose the one with minimum index1 out of them.

Input: [2, 7, 11, 15], target=9
Output: index1 = 1, index2 = 2

---

解題：

這題其實蠻簡單且直覺的，概念甚至比上一題更容易聯想：

尋找陣列L內兩數相加等於目標值T的索引值組合(L[i] + L[j] == T, i < j)
意即要在迴圈內尋找符合 L[j] == T - L[i] 之索引值 j
如無即表示當前迴圈訪問到的索引值為 i

而只需要一個 hashmap 可完美搞定上述要求，只是在迴圈推進過程中需注意依據輸入陣列值不同，可能會發生 L[0] == L[1] == L[5] 這種陣列內包含多個相同數值之情形，故在建立 hashmap 時須另建立機制排除後續出現的相同數值以符合題目要求。

Code:

class Solution:
    # @param A : tuple of integers
    # @param T : integer
    # @return a list of integers
    def twoSum(self, A, T):
        idxHash = dict()
        output = []
        for i in range(len(A)):
            try:
                output = [idxHash[A[i]]+1, i+1]
                break
            except:
                try:
                    idxHash[T-A[i]]
                    continue
                except:
                    idxHash[T-A[i]] = i
        return output

GitHub: GitHub