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

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

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

示例:

给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]

解题思路

首先想到的解决思路是通过两次循环，每次循环遍历列表，这种算法的时间复杂度是O(n^2)。

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

直接忽略这种解法。

我们接着会想到的做法就是，我们可以每次判断target-num[i]对应的值是否在num[i+1:]中。但是这里我们要注意一个问题，如果列表中有相同的元素，例如[3, 3]， 我们对应的target=6，这个时候我们在使用list.index的时候要注意index返回的是第一个值的位置，我们应该使用list[i + 1].index + i + 1。

class Solution:    def twoSum(self, nums, target):        """        :type nums: List[int]        :type target: int        :rtype: List[int]        """        len_nums = len(nums)        for i in range(len_nums):            dif = target - nums[i]                     if dif in nums[i+1:]:                 dif_index = nums[i + 1:].index(dif)+i+1                return [i, dif_index]        return []

上面做法虽然比第一种快，但是依旧不是最好的。我们思考一下，我们这种做法的问题有哪些，我们这里只用一次循环，但是循环中我们有查找操作（如果每次查找都是最差情况，那么我们要花O(n)的时间复杂度），并且查找索引的时候我们使用了index函数和切片操作，这些都是非常消耗时间的，那么我们有什么更加优秀的做法呢？

我们可以每次从nums[:i]中去查找是否有target - nums[i]。这种做法就避免了上述问题中的查找最差的情况（num_c是从空列表开始的）

class Solution:    def twoSum(self, nums, target):        """        :type nums: List[int]        :type target: int        :rtype: List[int]        """        nums_len = len(nums)        for i in range(nums_len):            dif = target - nums[i]            if dif in nums[:i]:                 return [nums.index(dif), i]        return []

我们分析这里存在的问题，我们现在的问题就只存在在list这个结构上了，因为我们无法再优化index和切片操作，那么有没有更加适合这个问题的数据结构呢?

我们就想到了哈希表这个结构，我们知道在python里面的map内部实现就是通过哈希表。我们可以通过哈希表来存储nums[:i]。关于哈希表的相关知识，大家可以看这篇

class Solution:    def twoSum(self, nums, target):        """        :type nums: List[int]        :type target: int        :rtype: List[int]        """        nums_hash = {
   }        nums_len = len(nums)        for i in range(nums_len):            dif = target - nums[i]            if dif in nums_hash:                 return [nums_hash[dif], i]            nums_hash[nums[i]] = i        return []

我们知道在c++中，unordered_map可以当作哈希表来使用，所以我在这里同时给出对应的c++版本。

class Solution{
   public:    vector
   
     twoSum(vector
    
     & nums, int target)     {
           unordered_map
     
       m;        for (int i = 0; i < nums.size(); ++i)        {
               if (m.count(target - nums[i]))            {
                   return {
   m[target - nums[i]], i};            }            m[nums[i]] = i;        }        return {
   };    }};
     
    
   

我将该问题的其他语言版本添加到了我的

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/80435039 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！