力扣刷题-哈希表两数之和

1 两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

思路

很明显暴力的解法是两层for循环查找，时间复杂度是O(n^2)。
当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。
本题呢，我就需要一个集合来存放我们遍历过的元素，然后在遍历数组的时候去询问这个集合（采用目标值减去当前值，然后判断这个差值是否在遍历元素集合中出现过，若出现过，那就去找对应的索引（nums.index(元素)）），某元素是否遍历过，也就是 是否出现在这个集合。——>哈希法

暴力法

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # 暴力法
        result = []
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    result.append(i)
                    result.append(j)
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

使用集合

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # 使用集合 比较巧妙
        seen = set() # 使用一个集合存储已经遍历的元素
        for i, num in enumerate(nums):
            complement = target - num # 求差值
            if complement in seen: # 如果刚好这个差值在遍历元素集合中 说明存在两个整数相加等于target
                return [nums.index(complement), i] # 返回对应索引 可以是任意顺序
            seen.add(num) # 添加num 不是complement

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15