c++ 两数之和

c++ 两数之和

题目：

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

暴力法

//nums.size()是获取数组的个数
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int i,j;
        for(i = 0; i <nums.size() - 1; i++){
            for(j = i + 1; j < nums.size(); j++){
                if(nums[j] == target - nums[i]){
                    return {i,j};
                
                }
            }
            
        }
        return {i,j};
        
    }
};

总结

该方法简单，但是时间复杂度为O(n²)，空间复杂度为O(1)，运行速度慢且内存空间消耗大。

两遍哈希表

// 向量 vector 是一种对象实体, 能够容纳许多其他类型相同的元素,称为容器，与string相同, vector 同属于STL(Standard Template Library, 标准模板库)
//中的一种自定义的数据类型, 可以广义上认为是数组的增强版。在使用它时, 需要包含头文件 vector, #include<vector>。
//vector 容器与数组相比其优点在于它能够根据需要随时自动调整自身的大小以便容下所要放入的元素。
//        vector<int> a ;                                //声明一个int型向量a
//        vector<int> a(10) ;                            //声明一个初始大小为10的向量
//        vector<int> a(10, 1) ;                         //声明一个初始大小为10且初始值都为1的向量
//        vector<int> b(a) ;                             //声明并用向量a初始化向量b
//        vector<int> b(a.begin(), a.begin()+3) ;        //将a向量中从第0个到第2个(共3个)作为向量b的初始值
//hash是键值对
//man<k,v>::key_type      在man容器中，k用做索引的键的类型
//man<k,v>::mapped_type   在man容器中，v用做键所关联的值的类型
//man<k,v>::value_type    

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> a;//建立hash表存放数组元素
        vector<int> b(2,-1);//存放结果  b中两个元素，初始化为-1
        for(int i = 0; i < nums.size(); i ++){
            a.insert(map<int,int>::value_type(nums[i],i));
        }
        for(int i = 0; i < nums.size(); i ++){
            if(a.count(target - nums[i]) > 0 && (a[target - nums[i]] != i)){
                //判断是否找到目标元素并且木变元素不能是本身
                b[0] = i;
                b[1] = a[target - nums[i]];
                break;
            }
        }
        return b;
    }
};

注：

该方法用map实现，map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力。

一遍哈希表

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> a;//建立hash表存放数组元素
        vector<int> b(2,-1);//存放结果  b中两个元素，初始化为-1
        for(int i = 0; i < nums.size(); i++){
            if(a.count(target - nums[i]) > 0 && (a[target - nums[i]] != i)){
                b[0] = a[target-nums[i]];
                b[1] = i;
                break;
            }
            a[nums[i]] = i; //放过来放入map中，用来获取结果下标
        }
        
        return b;  
    }
};

改进：

在进行迭代并将元素插入到表中的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回。