本文共 3171 字，大约阅读时间需要 10 分钟。

目录

题目描述

给定一个整数数组nums和一个目标值target，请你在该数据中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

输入/输出示例：

解决方案

方案一：二重循环检索

在二重循环里查找是否存在两个值的和与target相等。

for i in array:    for j in array:        if i + j == target:            # find!

如果找到满足条件的值，就讲对应元素的下标收集起来。最终将所有满足条件的下标所组成的列表返回。

但是这个方案有一个致命的缺点：时间复杂度为，也就是说大量的时间被浪费在重复的计算上，因此不是最优解。

方案二：使用字典和集合查找

减少无意义的循环嵌套是提高运行效率的方法。将数组存放在Python字典中，以数值为key，以索引为值，就可以使用两个叠加循环得解：

for index in range(len(nums)):    num_dict[nums[i]] = ifor value in num_dict:    if target - value in num_dict:        # find!

考虑到数组中可能出现多个相同的数值，因此字典的value应该是一个可迭代序列。我们选用查找时效较高的数据结构集合来作为value，即集合保存了数组中某个值的所有索引。

代码

class Solution(object):    def twoSum(self, nums, target):        """        :type nums: List[int]        :type target: int        :rtype: List[int]        """        nums_dict = {}        for i in range(len(nums)):            if nums[i] in nums_dict:                nums_dict[nums[i]].add(i)            else:                nums_dict[nums[i]] = set()                nums_dict[nums[i]].add(i)        result = set()        for value in list(nums_dict.keys()):            if (target - value) in nums_dict:                index1 = nums_dict[value].pop()                if len(nums_dict[value]) <= 0:                    del nums_dict[value]                try:                    index2 = nums_dict[target - value].pop()                except KeyError:                    continue                if len(nums_dict[target - value]) <= 0:                    del nums_dict[target - value]                result.add(index1)                result.add(index2)        return list(result)

代码走读

# LeetCode定义的解决方法类class Solution(object):    def twoSum(self, nums, target):        """        :type nums: List[int]        :type target: int        :rtype: List[int]        """        # 将数组结构保存在字典中，字典的key为数组中的每一个元素值，value是一个集合，保存了该值在数组中的全部索引        nums_dict = {}        for i in range(len(nums)):            if nums[i] in nums_dict:                nums_dict[nums[i]].add(i)            else:                nums_dict[nums[i]] = set()                nums_dict[nums[i]].add(i)        # 将结果放入集合中，避免将重复的数据输出        result = set()        # 遍历字典        for value in list(nums_dict.keys()):            # 如果有存在要求的两个值，则将两个值对应的索引弹出。如果索引集合内长度为空，将该key从字典中删除            if (target - value) in nums_dict:                index1 = nums_dict[value].pop()                if len(nums_dict[value]) <= 0:                    del nums_dict[value]                # 捕捉这个异常是因为数组中存在某个数刚好是目标值target的一半，但巧合的是该值只存在一个，没有配对的另一个值                # 因此index1可以获取到下标，但是会将该key在字典中删除，导致index2在获取中抛出异常KeyError                try:                    index2 = nums_dict[target - value].pop()                except KeyError:                    continue                if len(nums_dict[target - value]) <= 0:                    del nums_dict[target - value]                # 将获取到的两个下标添加到结果集合中                result.add(index1)                result.add(index2)        # 转换成题目要求输出的格式返回        return list(result)# 自测用例if __name__ == '__main__':    result = Solution().twoSum([3, 3], 6)    print(result)

传送门

转载地址：http://ndsoi.baihongyu.com/