题目

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解法一(自己的思路，一般人都会想到的方法，暴力求解)

使用多个循环进行求解

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        int temp = 0;
        for( int i=0;i < nums.size() ; ++i ){
            temp = target - nums[i] ; //判断差值在后面的数据中是否能找到
            for( int j=i+1;j < nums.size();++j){
                if(temp == nums[j]){
                    result.push_back(i);
                    result.push_back(j);
                    exit;
                }
            }
            if(result.size()>0) exit; // 只计算第一个满足的结果即可
        }
        return result;
    }
};

解析：
该方法
时间复杂度: O(n^2), 对于每个元素而言，通过遍历数组中的其他部分来寻找对应的目标元素，这将耗费O(n)的时间，然而对于每个元素都要耗费O(n)的时间，所以整体需要消耗O(N^2)的时间。
空间复杂度: O(1). 由于内存不会随随着元素的增多而增多。

解法二 (使用哈希表) 不熟 主要不太知道哈希表的概念是什么

使用了非排序的map进行查询确定要快点？？？

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> hashmap;
    vector<int> res;
    
    for(int i = 0; i != nums.size(); i++)
    {
        int gap = target - nums[i];
        if(hashmap.find(gap) != hashmap.end())
        {
            res.push_back(i);
            res.push_back(hashmap[gap]);
            break;
        }
        hashmap[nums[i]] = i;
    }
    return res;  
    }   
};

复杂度分析:

时间复杂度: O(N). 只遍历了一遍列表中的n个元素，而在在unordered_map 查询的时间复杂度为O(log(n)),而hash_map查询时间复杂度为O(1).
空间复杂度: O(N). 需要额外的空间来存储取决哈希表中的元素数量，元素数量最大为n个.

知识点

哈希表 以(key , value)形式成对出现的数据结构，通过把关键字(key)映射到表中一个位置用来访问，以加快查找的速度。

map 与 哈希表不相同 。 c++ 的标准函数库中没有哈希表函数，故使用unordered_map函数 其查询时间复杂度为O(log(N)).