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)


相关推荐

发表回复

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

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