【LeetCode】1.两数之和（Python3）

来源

https://leetcode-cn.com/problems/two-sum

难度

简单

标签

array | hash-table

公司

adobe | airbnb | amazon | apple | bloomberg | dropbox | facebook | linkedin | microsoft | uber | yahoo | yelp

描述

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

你可以假设每种输入只会对应一个答案。但是&＃xff0c;数组中同一个元素在答案里不能重复出现。

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

示例

示例 1&＃xff1a;

输入&＃xff1a;nums &＃61; [2,7,11,15], target &＃61; 9
输出&＃xff1a;[0,1]
解释&＃xff1a;因为 nums[0] &＃43; nums[1] &＃61;&＃61; 9 &＃xff0c;返回 [0, 1] 。


示例 2&＃xff1a;

输入&＃xff1a;nums &＃61; [3,2,4], target &＃61; 6
输出&＃xff1a;[1,2]


示例 3&＃xff1a;

输入&＃xff1a;nums &＃61; [3,3], target &＃61; 6
输出&＃xff1a;[0,1]


提示

• 2 $<\&＃61;$ nums.length $<\&＃61;$ 10410^4104
• -10910^9109 $<\&＃61;$ nums[i] $<\&＃61;$ 10910^9109
• -10910^9109 $<\&＃61;$ target $<\&＃61;$ 10910^9109
• 只会存在一个有效答案

进阶

你可以想出一个时间复杂度小于 O(n2n^2n2) 的算法吗&＃xff1f;

提交

提交1&＃xff1a;&＃xff08;暴力求解&＃xff09;

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:for i in range(len(nums)-1):for j in range(i&＃43;1, len(nums)):if nums[i]&＃43;nums[j] &＃61;&＃61; target:return [i, j]


提交2&＃xff1a;&＃xff08;哈希表法&＃xff09;

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:dict &＃61; {}for i in range(len(nums)):if target-nums[i] in dict:return [dict[target-nums[i]], i]else:dict[nums[i]] &＃61; i


题解

https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-solution/