文山专业网站建设报价,网站建设一条龙全包,怎么做微信公众号小程序,沂水网站制作文章目录题目描述题目难度——简单方法一#xff1a;暴力代码/Python方法二#xff1a;哈希表代码/Python代码/C总结题目描述 这道题可以说是力扣的入坑题了#xff0c;很经典#xff0c;好像还是面试的经典题。 给定一个整数数组 nums 和一个整数目标值 target#xff0c…
文章目录题目描述题目难度——简单方法一暴力代码/Python方法二哈希表代码/Python代码/C总结题目描述 这道题可以说是力扣的入坑题了很经典好像还是面试的经典题。 给定一个整数数组 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[i] 109-109 target 109只会存在一个有效答案 进阶你可以想出一个时间复杂度小于 O(n2) 的算法吗
题目链接
题目难度——简单
方法一暴力 最简单的方法就是无脑暴力虽然看数组长度可能会失败但平均下来找到答案时两个下标的差距的期望应该不大可以暴力一试。用两个循环每次判断两个数相加是否为target。
代码/Python
class Solution:def twoSum(self, nums: List[int], target: int) - List[int]:res []n len(nums)for i in range(n):for j in range(n):if i ! j and nums[i] nums[j] target:res.append(i)res.append(j)return resreturn [-1, -1] 方法二哈希表 我们可以只用一次循环就找到答案在一次遍历中对每个x问题可以变成在数组中找target-x的坐标如果我们能知道过去遍历过的数的位置i那么答案就显然是当前位置和i否则我们继续往前遍历并记录当前元素的位置。所以我们需要一个字典。
代码/Python
class Solution:def twoSum(self, nums: List[int], target: int) - List[int]:res [-1, -1]n len(nums)pos dict()for i in range(n):tmp target - nums[i]if tmp in pos:res[0], res[1] i, pos[tmp]return reselse:pos[nums[i]] ireturn res 代码/C
class Solution {
public:vectorint twoSum(vectorint nums, int target) {vectorint res(2);unordered_mapint, int pos;int i, tmp;for(i 0; i nums.size(); i){tmp target - nums[i];if(pos.count(tmp) ! 0){res[0] i;res[1] pos[tmp];return res;}else{pos[nums[i]] i;}}return res;}
};总结 第一种暴力所以时间是O(N2)空间是O(1)第二种遍历一次时间是O(N) 使用了字典所以空间是O(N)。
