首页 > 其他分享 >1-两数之和

1-两数之和

时间:2023-03-31 09:33:07浏览次数:32  
标签:target nums int re vector 数组 两数

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

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

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

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

最朴素的解法就是暴力解法:
先确定一个数,然后在数组中找另一个数是否符合要求

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

如何改进?
寻找另一个数,也就是查找算法,可以有O(1) 的算法或者数据结构 那就是哈希表

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> re;
        unordered_map<int,int> map;
        for (int i = 0; i < nums.size();i++){
            map.insert({nums[i],i});
        }
        for (int i = 0;i<nums.size();i++){
            int a = nums[i];
            int b = target - a;
            auto it =map.find(b) ;
            if (it != map.end()){
                // find it but not be itself
                if (it->second == i){
                    continue;
                }
                re.push_back(i);
                re.push_back(it->second);
                return re;
            }
        }
        return re;
    }
};

对整个数组建立好哈希表,但是在查找过程中不能找到它本身,题目要求,每个数只能用一次,所以要用if判断下查找出来的这个值是不是它本身

标签:target,nums,int,re,vector,数组,两数
From: https://www.cnblogs.com/MartinTai/p/17275205.html

相关文章

  • 两数组的交集|哈希集
    两个数组的交集寻找两个数组相同的元素,注意返回元素的唯一性对应题目349.两个数组的交集哈希集合使用两个哈希集合,第一个保存前一个数组的元素,第二个集合遍历第二个......
  • #yyds干货盘点# LeetCode程序员面试金典:两数之和
    题目:给定一个整数数组nums 和一个整数目标值target,请你在该数组中找出和为目标值target 的那 两个 整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答......
  • 算法-两数之和
    给定一个整数数组nums 和一个整数目标值target,请你在该数组中找出和为目标值target 的那 两个 整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案......
  • 2.两数相加
    给你两个非空的链表,表示两个非负的整数。它们每位数字都是按照逆序的方式存储的,并且每个节点只能存储一位数字。请你将两个数相加,并以相同形式返回一个表示和的链表......
  • 代码随想录Day5-Leetcode242.有效的字母异位词,349. 两个数组的交集,202. 快乐数,1. 两数
    242.有效的字母异位词准备面试隔了三天没刷题,结果面试里就考到哈希表了,也是蛮感叹的.简单题,不过api又忘的差不多了这道可以用数组手动实现一个简易哈希表,但(因为......
  • day6(day5休息) | 1. 两数之和; 202. 快乐数; 242. 有效的字母异位词; 349. 两个数组
    1.两数之和 题目简述 给定一个整数数组nums和一个整数目标值target,请你在该数组中找出和为目标值target的那两个横竖,并返回他们的数组下标。 你可以假设每种输入......
  • LeetCode 2.两数相加
    题目链接在这里:​​2.两数相加-力扣(LeetCode)​​这道题学了一些python类和子函数的语法,发现语法与C++有异曲同工之妙1classListNode:2def__init__(self,val=0,......
  • Leetcode 1.两数之和(hash)
    题目链接在这里:​​1.两数之和-力扣(LeetCode)​​这道题主要学习了python中哈希表的使用,类似于c++中的map容器1#暴力2#classSolution:3#deftwoSum(self,nu......
  • LeetCode1. 两数之和
    题目描述:给定一个整数数组nums 和一个整数目标值target,请你在该数组中找出和为目标值target 的那 两个 整数,并返回它们的数组下标。你可以假设每种输入只会对应......
  • Leetcode 1.两数之和(hash)
    题目链接在这里:1.两数之和-力扣(LeetCode)这道题主要学习了python中哈希表的使用,类似于c++中的map容器1#暴力2#classSolution:3#deftwoSum(self,num......