leetcode-LC1

两数之和给定一个整数数组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]解法1暴力遍历两遍class Solution(object): def twoSum(self, nums, target): :type nums: List[int] :type target: int :rtype: List[int] #先设计一个放最后的结果的数组就是[01]这样的 result[] #接下来就是遍历两遍第一遍从头遍历每个数字都取一遍 #第二个数字是和第一个进行匹配加起来能够等于target的数字 for i in range(0,len(nums)): for j in range(i1,len(nums)): total nums[i]nums[j] #现在分析当前结果是否是taget if total target: result.append(i); result.append(j); return result return res解法2使用哈希表哈表是 key | Value的形式 那么key对应当前元素的值Value对应索引class Solution(object): def twoSum(self, nums, target): :type nums: List[int] :type target: int :rtype: List[int] #首先设置一个存储最后的结果的数组 result [] #其次需要设置一个哈希表 mapping {} #先整体遍历一遍当前的数组的数值把表中的每个数值全部都存入哈希表中 for i in range (0,len(nums)): mapping[nums[i]] i #完成哈希表的遍历存储完成找每个数值与target的差值如果差值在哈希表中存在那么就是目标的两个数 for j in range(0,len(nums)): #求当前的数值和target的差值 diff target - nums[j] #寻找当前的哈希表中是否有有索引对应目标diff if (diff in mapping and mapping[diff] ! j): #题目的要求是不可以是当前的这个num[j]本身mapping[diff] ! j result.append(j) result.append(mapping[diff]) return result当前设计找匹配nums[j] 的加和为target的值的时候只需要在哈希表中找复杂度O(1)