【LeetCode面试150】—

【LeetCode面试150】——1两数之和

embedded/2024/11/23 7:52:40/

博客昵称：沈小农学编程

作者简介：一名在读硕士，定期更新相关算法面试题，欢迎关注小弟！

PS：哈喽！各位CSDN的uu们，我是你的小弟沈小农，希望我的文章能帮助到你。欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！😘

题目难度：简单

默认优化目标：最小化时间复杂度。

Python默认为Python3。

1 题目描述

2 题目解析

3 算法框架及程序实现

3.1 暴力求解

3.2 哈希表

参考文献

1 题目描述

给定一个整数数组 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

只会存在一个有效答案

2 题目解析

输入是一个整数数组nums，一个目标求和整数target。输出是一个整数数组ans，其元素代表的是nums对应的下角标。约束条件是nums[ans[i]]之和等于target。

3 算法框架及程序实现

两数之和等于target，我们转换思路，target减去其中的一个数就等于另一个数，这就把问题转换成了查找。查找最快的是用哈希表。

3.1 暴力求解

两次循环找nums[i]+nums[j]=target。

C++ 代码实现

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

Python代码实现

python">class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:for i,num_i in enumerate(nums):for j in range(i+1,len(nums)):if(num_i+nums[j]==target):return [i,j]return []

3.2 哈希表

哈希表table的key为整数，value为其在nums种出现的位置。我们在哈希表中找target-nums[i]的整数，找到返回其对应的value,i。

C++ 代码实现

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int,int> table;for(int i=0;i<nums.size();i++){auto it=table.find(target-nums[i]);if(it!=table.end()){return {it->second,i};}table[nums[i]]=i;//哈希表填充}return {};}
};

Python代码实现

python">class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:table=dict();for i,num in enumerate(nums):if target-num in table:return [table[target-num],i]table[nums[i]]=ireturn []