【LeetCode面试150】—

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

博客昵称：沈小农学编程

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

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代码实现

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代码实现

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]]=i
        return []