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

46 阅读 0 评论 31 点赞

我是靠谱客的博主默默灰狼，最近开发中收集的这篇文章主要介绍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 (n)

的时间。因此时间复杂度为

-空间复杂度：

//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;  
}