LeetCode第一题:两数之和-C++

LeetCode第一题:两数之和-C++自己的解答(简单的遍历所有可能的组合,找到最终的结果):【不是特别熟悉C++,先有一个vector的插入:vector.puch_back(),主要是各种运用的不熟练,希望能有改进】给出简单代码:classSolution{public:vector<int>twoSum(vector<int>&nums,inttarget){…

大家好,又见面了,我是你们的朋友全栈君。

LeetCode第一题:两数之和-C++
自己的解答(简单的遍历所有可能的组合,找到最终的结果):

【不是特别熟悉C++,先有一个vector的插入:vector.puch_back(),主要是各种运用的不熟练,希望能有改进】
给出简单代码:
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> twoSum;
        for(int i=0;i<nums.size();i++){
            for(int j=i+1;j<nums.size();j++){
                if((nums[i]+nums[j])==target){
                    twoSum.push_back(i);
                    twoSum.push_back(j);
                }
            }
        }
    return twoSum;
    }
};

复杂度分析:

-时间复杂度:
O(n2), 对于每个元素,我们试图通过遍历数组的其余部分来寻找它所对应的目标元素,这将耗费
O(n)O(n)O(n)的时间。因此时间复杂度为
O(n2)。
-空间复杂度:
O(1)。

二、官方优化:
//C++ hash_map 用法示例:
#include <map>
#include <string>
using namespace std;

map<string, string> namemap;
//增加。。。
namemap["岳不群"]="华山派掌门人,人称君子剑";
namemap["张三丰"]="武当掌门人,太极拳创始人";
namemap["东方不败"]="第一高手,葵花宝典";

//查找。。
if(namemap.find("岳不群") !=namemap.end()){ ...}

–哈希表:

//哈希表

vector<int> twoSum(vector<int>& nums, int target) {
      vector<int> twoSum;
      map<int, int> tmpmap;//键值为nums的值,变量值为nums下标
        for (int i = 0; i < nums.size(); i++) {
          tmpmap[nums[i]] = i;
      }
      for (int i = 0; i < nums.size(); i++) {
          if (tmpmap.count(target - nums[i]) != 0 && tmpmap[target-nums[i]]!=i) {//  如果目标值减去循环到的值对应的下标不为0,或者不为i,【存在有另一个数与循环值相加等于target,则返回结果】
            twoSum.push_back(i);
              twoSum.push_back(tmpmap[target - nums[i]]);
              break;
          }
      }
      return twoSum;
  }  

–哈希表优化版:

vector<int> twoSum(vector<int>& nums, int target) {  
    vector<int> twoSum;  
    map<int, int> tmpmap;//键值为nums的值,变量值为nums下标  
  
    for (int i = 0; i < nums.size(); ++i) {  
        if (tmpmap.count(nums[i]) != 0) {  
            twoSum.push_back(tmpmap[nums[i]]);  
            twoSum.push_back(i);  
            break;  
        }  
        tmpmap[target - nums[i]] = i;  
    }  
    return twoSum;  
}  

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/136472.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • Oracle数据库备份与恢复方案

    Oracle数据库备份与恢复方案任何数据库在长期使用过程中,都会存在安全隐患。对于数据库管理员来说不能仅寄希望于计算机操作系统的安全运行,而是要建立一整套的数据库备份与恢复机制。当任何人为的或是自然的灾难一旦出现,而导致数据库崩溃、物理介质损坏等,就可以及时恢复系统中重要的数据,不影响整个单位业务的运作。然而如果没有可靠的备份数据和恢复机制,就会带来系统瘫痪、工作停滞、经济损失等等不堪设想的后果。本文以ORACLE数据库为例,结

  • PyTorch学习笔记(6)——DataLoader源代码剖析

    PyTorch学习笔记(6)——DataLoader源代码剖析这两天把DataLoader的源代码的主要内容进行了一些分析,基于版本0.4.1。当然,因为内容比较多,没有全部展开,这里的主要内容是DataLoader关于数据加载以及分析PyTorch是如何通过Python本身的multiprocessing和Threading等库来保证batch是顺序取出的。额外的内容都会给出链接,在这里不会详细展开。0.前言(楔子)本篇关于DataLoad…

  • 4种kill某个用户所有进程的方法

    4种kill某个用户所有进程的方法

  • MATLAB分段函数及应用实例

    MATLAB分段函数及应用实例简单实例:用matlab画分段函数        当x&lt;0时 y=5*sin(x);        当x&gt;=0且x&lt;=5时y=x^2;        当x&gt;5时y=(8-x)^2+16.x=-5:0.001:10;y=5*sin(x).*(x&lt;0)+x.^2.*(x&gt;=0&amp;x&lt;=5)+((8-x).^2+16).*(x&gt;5);p…

  • mac 安装golang2021 激活码_在线激活

    (mac 安装golang2021 激活码)2021最新分享一个能用的的激活码出来,希望能帮到需要激活的朋友。目前这个是能用的,但是用的人多了之后也会失效,会不定时更新的,大家持续关注此网站~IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html…

  • SpringCloud—熔断器Hystrix的作用–解决灾难性雪崩效应

    SpringCloud—熔断器Hystrix的作用–解决灾难性雪崩效应

    2020年11月12日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号