leetcode 1 -- Two Sum

leetcode 1 – Two Sum

最近打算开始练习下leetcode上面的题，原因有2点
- 1.保证自己每天有敲一定的代码练习，避免手生。
- 2.锻炼自己的思维能力吧，思维还是很重要的。

---

题目：
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

---

题意：
题目意思是给一组数据和一个目标值，让你找到这组数据中 和 加起来等于目标target的两个数的下标index1和index2。

---

思路：
常规的暴力求解法肯定可以，也很好想到，一个一个测试，时间复杂度是O(n^2)，但数据量大就不行了，所以想到需要用类似hash的能快速索引到我们想要找到的数字的数据结构，我用的是c++STL中的map，内部基于红黑树的一种查找树，且有映射功能，对于每个数据nums[i]，把它对应的target-nums[i]存储在map中，且映射nums[i]的下标，这样如果数据中接下来出现了targer-nums[i]这个数据，我们就能快速得到它们俩的下标分别为i和map(target-nums[i])。

---

代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //返回值
        vector<int>ret;
        //建立映射
        map<int,int>mp;
        for(int i = 0; i < nums.size(); ++i){
            //在map中查找，如果找到说明之前出现过对应的值
            if(mp.find(nums[i]) == mp.end()){
                mp[target - nums[i]] = i;
            }else{
                ret.push_back(mp[nums[i]]+1);
                ret.push_back(i+1);
            }
        }
        return ret;
    }
};

---

最后说一句，刚开始做题时，题目会自动有个模板
如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
    }

这其实是让我们写核心代码即可，参数和返回值以及框架都给定了。我们只需要把过程填进twoSum这个函数就好了，我刚开始就把这个删除了，重新定义头文件和main函数开始写- -，这样是不对的。
写下来希望能帮到和我一样的刷题新手~
祝大家刷题都是

哈哈^_^