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

编程汇总 • 2025-03-26 07:21 • 阅读 72

自己的解答（简单的遍历所有可能的组合，找到最终的结果）：

【不是特别熟悉C++，先有一个vector的插入：vector.puch_back()，主要是各种运用的不熟练，希望能有改进】

给出简单代码：

class Solution {

public:

    vector twoSum(vector& nums, int target) {

        vector twoSum;

        for(int i=0;i
            for(int j=i+1;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 

#include 

using namespace std;



map namemap;

//增加。。。

namemap["岳不群"]="华山派掌门人，人称君子剑";

namemap["张三丰"]="武当掌门人，太极拳创始人";

namemap["东方不败"]="第一高手，葵花宝典";



//查找。。

if(namemap.find("岳不群") !=namemap.end()){ ...}

–哈希表：

//哈希表

vector twoSum(vector& nums, int target) {

      vector twoSum;

      map 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 twoSum(vector& nums, int target) {  

    vector twoSum;  

    map 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;  

}

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

相关推荐