twosum_twosum(vector& nums, int target)

twosum

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> m;
        const int size=nums.size();
        int tmp;

        for (int i=0;i!=size;++i){
            tmp=nums[i];
            if (m.find(tmp)!=m.end()){
                return {m[tmp],i};
            }
            m[target-tmp]=i;
        }
        return {-1,-1};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

题目分析
给定一数组，返回数组中两数的索引（下标），是的两数和为特定目标值。
假定每组输入都有一特定输出值，且元素不会出现两次。
解题思路
基本思路：
对每个数num[i],求出rest=target-num[i]，然后在数组中查找rest是否存在。
时间复杂度$o(n^2)$
散列法：
使在一个数列中查询一个数是否存在的时间复杂度为o(1)
本题思路
把给定的数组散列到一个比较大的数组中，每次查询的时间复杂度为o(1),总复杂度o(n). n表示输入数组的长度。
本题使用的是矢量，无长度限制。
在c++11标准中，在标准STL库添加了unordered_map,这是给与哈希表的图，区别于STL的map（基于平衡二叉树）

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int>ans;
        unordered_map<int,int>myMap;
        unordered_map<int,int>::iterator it;

        int len=mums.size();
        for(int i=0;i<len;i++){
            it=myMap.find(target-nums[i]);
            if(int i=0;i<len;i++){
                it=myMap.find(target-nums[i]);
                if(it!=myMap.end()){
                    ans.push_back(it->second);
                    ans.push_back(i);
                    return ans;
                }
                myMap[num[i]]=i;

            }
            return ans;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24