2022-10-09 两数之和

力扣题目：Link

map的结构

map是一种<key,value>的存储结构，可以用key保存数值，用value保存数值所在的下标。

插入操作：

map.insert(pair<int,int>(nums[i], i));

iter指针

在<key,value>结构中，iter指针的意义：

iter->first     // key
iter->second    // value

解题思路

利用<key,value>的结构特性加上unordered_map的底层实现特性（hash table），我们可以直接进行先查找后插入的方式来进行搜索匹配。

时间复杂度为O(n)。

代码实现

具体代码如下：

/* LeetCode Question No.1
 * Given an array of integers `nums` and an integer `target`, return indices of
 * the two numbers such that they add up to `target`.
 * You may assume that each input would have exactly one solution, and you may
 * not use the same element twice.
 * You can return the answer in any order.
 */

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // The storage arch of `map` is <key,value>,
        // which save number-value with `key`,
        // and save index with `value`.
        std::unordered_map <int, int> map;
        for (int i = 0; i < nums.size(); i++) {
            auto iter = map.find(target - nums[i]);
            if (iter != map.end()) {
                return {iter->second, i};   // iter->first is key;
                                            // iter->second is value;
            }
            // insert a pair of integer values into the map
            map.insert(pair<int,int>(nums[i], i));
        }
        return {};
    }
    void printV(vector<int> nums){
        for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++) {
            cout << *it << " ";
        }
        cout << endl;
    }
};

int main(void){
    vector<int> nums = {1, 2, 3, 4, 5};
    int target = 0;

    Solution sl;

    cout << "0\t1\t2\t3\t4\t" << endl << "1\t2\t3\t4\t5\t" << endl;
    cout << "Please return your target smaller than 9: ";
    cin >> target;

    sl.printV(sl.twoSum(nums, target));
}