LeetCode从零刷起 (1. Two Sum)

2017.3.27 刷题开始

博主最近忙于找实习，发现不少互联网的大公司，在线笔试以及面试中都会考一些基本的编程题目，而LeetCode正是收集这些题目的一个平台，所以博主决定从零刷起，希望有兴趣的小伙伴互相鼓励，共同进步。
由于博主是博客小白，所以博客中的不成熟之处还请大家批判指正。LeetCode的刷题顺序处于摸索状态，目前是按照题号从易到难。这种网上OJ也是第一次开始刷，个人原创的算法中难免有不成熟之处，还希望大家多多指点。
闲话少说，直奔主题。

LeetCode（1.Two Sum）

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].

知识点：
这道题应用了hash表的知识，具体用法可参见 C++ Reference；此外，我注意到LeetCode对vevtor的使用也比较多，题主此前对vector这个数据结构并不熟悉，所以此处也要强调一下，具体用法参见C++ Reference。

解题思路：
首先建立一个从int到int映射的hash表，将nums中的元素每一个都映射到hash表中。然后从头开始遍历nums，查找目标元素值是否在hash表中，如果没有则继续查找；如果有的话判断一下两个元素的下标是否相同，避免出现下标相同的情况。C++代码如下：

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

时间复杂度分析：
该算法时间复杂度为O(n)。建立hash表的时间复杂度为O(n)；遍历nums在hash表中查找的时间复杂度也为O(n)。所以，整个算法的时间复杂度为O(n)。