LeetCode 1 两数之和

题目

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

代码

def twoSum(nums, target):
    """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
    #         for i in range(len(nums)-1):
    #             for j in range(i+1,len(nums)):
    #                 if nums[i] + nums[j] == target:
    #                     return [i,j]
    dic = {}
    for i, num in enumerate(nums):
        print(nums)
        if num in dic:
            print('----')
            print([dic[num], i])
            print('----')
        else:
            dic[target - num] = i
            print(dic)

twoSum([1,3,5], 8)

原理解析:

将目标值t与当前遍历的元素num做差,将差值和num的索引值i存入字典dic,
当取到下一个num值时,先检查num 有没有在dic中,
如果存在,说明已经找到了两个num 满足相加等于t的条件(a+b=c => a=c-b)
然后返回当前num的索引值和之前存入字典的索引值