经Derek提醒,可用dict来存每个integer的初始位置。需注意num=[0,4,3,0], target=0这种两加数相等的情况。

class Solution:
    # @return a tuple, (index1, index2)
    def twoSum(self, num, target):
        lenNum = len(num)
        d = {} # key is integers in the given array, value is a list of their original index, one key may have 1 or 2 index
        for i in xrange(lenNum):
            d[num[i]] = [i + 1] if num[i] not in d else d[num[i]] + [i + 1]
        for i in num:
            if target - i in d:
                if i == target - i:
                    if len(d[i]) == 2: return (d[i][0], d[i][1])
                else:
                    return (d[i][0], d[target - i][0]) if d[i][0] < d[target - i][0] else (d[target - i][0], d[i][0])