[刷题笔记]LeetCode1. Two Sum

Descripition

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
给定一个整形数组，返回相加等于指定目标数字的元素下标，
假设每组输入恰好只有一种可能的解，并且同一元素不能使用两次。

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

分析

遍历一遍数组，遍历的同时，用一个map记录经过的数字与下标，每遇到一个新的元素，查找目标值与该元素的差是否存于在map中，若存在则返回对应下标，否则继续遍历。

最坏情况需一次遍历和正比数组长度的额外空间，因此时间复杂度和空间复杂度均为O(n)。

C++ Code:

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