【LeetCode】1. 两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一暴力法

两层循环遍历所有可能的组合，当两数和等于target时返回

时间复杂度 $O(n^2)$

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums) - 1):
            for j in range(i+1, len(nums)):
                if target == (nums[i] + nums[j]):
                    return [i, j]

解法二 Hash法

遍历每个元素，用字典保存target减当前元素的结果和当前索引

如果字典内存在与当前元素值相等的key 时，返回key对应的value及当前索引
否则，将 (target - value): 索引作为键: 值对存入字典

典型的空间换时间的算法

遍历一次即可，每一次循环的操作时间复杂度是 $O(1)$ ，因此总的时间复杂度是 $O(n)$ ，空间复杂度是 $O(n)$

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        _dict = {}
        for i, num in enumerate(nums):
            if num in _dict.keys():
                return [_dict[num], i]
            else:
                _dict[target - num] = i

【LeetCode】1. 两数之和

解法一 暴力法

解法二 Hash法

解法一暴力法