1. 两数之和

Gnomeshgh

一、题目描述

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。



示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]


提示：

2 <= nums.length <= 104
-109 <= nums <= 109
-109 <= target <= 109
只会存在一个有效答案


二、解题思路

（一）暴力解法


最直观的方法就是穷举，对每一个数据进行两两相加，判断是否与目标值相等，相等则返回该下标。

1. class Solution:
   
2.     def twoSum(self, nums: List[int], target: int) -> List[int]:
   
3.         # 第一个下标从0到倒数第二个
   
4.         for i in range(len(nums) - 1):
   
5.             # 第二个下标从i + 1 到倒数第一个
   
6.             for j in range(i + 1 , len(nums)):
   
7.                 # 与目标值一致则直接返回
   
8.                 if nums[i] + nums[j] == target:
   
9.                     return [i , j]
   
10.         # 没有符合的就返回空
    
11.         return []

复制代码

简单地优化一下，遍历的目的就是找到两数相加等于目标值，已知目标值，以及初始下标，相减即可得到需要找的值，可以直接用python中的count直接判断是否大于0即可，大于0则说明存在。还需注意的是一个值不能用两次，所以还要进行是否是自身的判断。

1. class Solution:
   
2.     def twoSum(self, nums: List[int], target: int) -> List[int]:
   
3.         left = 0 # 记录起始下标
   
4.         right = len(nums) # 记录终止下标
   
5.         while left < right: # 当超出范围时结束循环
   
6.             if nums.count(target - nums[left]) != 0: # 查询该列表中是否有相配对的数，有则不为0
   
7.                 if left != nums.index(target - nums[left]):# 若这个数不是它本身则说明，找到了相配对的数
   
8.                     return [left,nums.index(target - nums[left])]# 返回其对应得下标
   
9.             left = left + 1 # 没有符合得就下标加1
   
10.         return [] # 都没有符合得就返回空列表

复制代码

（二）哈希表法

哈希表非常适合查找类的题目，这个题目可以用思路二进行查找转换。
首先是创建哈希表，可以用enumerate进行创建，这样可以使值和下标同时存在且可以访问

1. class Solution:
   
2.     def twoSum(self, nums: List[int], target: int) -> List[int]:
   
3.         # 创建一个空集合，用于哈利表的存储
   
4.         hash_map  = {}
   
5.         # enumerate(nums),会转换为二元组，i取下标，num取值
   
6.         for i,num in enumerate(nums):
   
7.             # 判断目标值是否存在于哈希表中
   
8.             if target - num in hash_map:
   
9.                 return [i,hash_map[target - num]]
   
10.             # 不存在则就向哈希表中添加元素，此时键为num，值为i，这样方便返回下标
    
11.             hash_map[num] = i
    
12.         # 都不存在则返回空
    
13.         return []

复制代码

不二如是

不错！！欢迎分享