前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >计算两个数的和算法

计算两个数的和算法

作者头像
玖柒的小窝
修改2021-12-24 11:38:35
6000
修改2021-12-24 11:38:35
举报
文章被收录于专栏:各类技术文章~

一、题意

给定一个整数数组 nums 和一个整数 target ,找到数组里的两个数的和等于 target,返回这两个数在数组中的下标,假设每个输入都只有一个解决方案,并且不能两次使用相同的元素。可以按任何顺序返回答案。

注意:数组无序。

二、测试样例

输入: nums = [2,7,11,15], target = 9

输出: [0,1]

解释:因为 2 + 7 = 9,数字 2和7的在数组中的下标分别为 0和1,所以输出 [0,1]。

二、解题思路

遍历数组 nums,使用哈希表(unordered_map类型)存储数组中遍历过的元素,每遍历一个元素 nums[i],查找哈希表中是否存在 target - nums[i],如果不存在,则将 nums[i] 和 下标 i 存储到哈希表中,如果存在,则返回当前下标以及哈希表中 target - nums[i] 对应的值。

通俗一点的说就是:每次在哈希表中查找 target - nums[i] 是否存在,一直查询到一个结果。

三、代码实现

代码语言:javascript
复制
class Solution
{
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        unordered_map<int, int> hashTable; //哈希表
        vector<int> ret;
        for(int i = 0; i < (int)nums.size(); ++i) { //依次遍历每一个元素
            if(hashTable.count(target - nums[i])) {//查找 target - nums[i] 是否存在
                ret.push_back(i); // 存储下标
                ret.push_back(hashTable[target - nums[i]]); //存储下标
                return ret;
            } 
            hashTable[nums[i]] = i;
        }
        return ret;
    }
};

四、时间复杂度分析

时间复杂度:使用哈希表存储,每次查询的时间是O(1),最多遍历 n 个元素,故时间复杂度为 O(n)。

本文系转载,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文系转载前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、题意
    • 二、测试样例
      • 二、解题思路
        • 三、代码实现
        • 四、时间复杂度分析
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档