LeetCode_#1 Two Sum

---

今天正式开启我的 LeetCode 刷题之旅～        作为一只算法菜鸡，遇到题目只能想到效率最低的方法的我深知写出好的算法的重要性。就以前学习的基础算法而言，同样是排序算法，一个冒泡排序和一个快速排序在面对上万的随机生成数时，其解决所消耗时间的差距之大令人瞠目。所以本菜鸡决定定期刷一刷题库以提高自己的算法修为。

---

进入 LeetCode 的 problem 首页，就看见了标号为 #1 的题目 Two Sum，难度为 easy。

本菜鸡暗自窃喜，如此容易的题目正好拿来热热身～

• 题目

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

因为寒假在学习cpp，所以就选择它来练习练习。提交框中已经给定了框架：

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

题目大意为给你一组整形值，让你编写函数返回其中两个加起来等于给定数目的数，每次的数据只会有一种答案，并且给定的数据中没有重复的值。

根据给定的函数原型，twoSum 接受一个元素为 int 的 vector 对象的引用和一个整形值，分别代表给定的一组数据和要求两数相加等于的特定整数，函数返回一个 vector ，当然是包含答案里的两个数值。

根据本菜鸡的惯性思维，第一个想到的是用 for 语句嵌套，匹配出所有可能组合，再和 target 比较。好在我留了个心眼，尽我之所能稍微的优化了一下，及：当找到需要的值后，退出循环并且返回。

此种算法的时间复杂度为 O(n^2)，具体实现如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
                for(auto index = nums.begin(); index != nums.end()-1;
                                ++index){
                        bool flag = false;
                        for(auto check = index+1; check != nums.end();
                                        ++check)
                                if(*index+*check == target){
                                        result.push_back(index-nums.begin());
                                        result.push_back(check-nums.begin());
                                        flag = true;
                                        break;
                                }
                        if(flag) break;
                }
                return result;
    }
};

满脸得意的去提交——

AC 是 AC 了，刚舒了一口气，一看数据，傻了。敲了半天是 AC 里的垫底。。。

于是乎去网上大神们的博客里取经，得到一种优化方法，其思路如下：

两个数相加等于特定的数，小学生也会知道这个特定的数减去其中一个数就等于另一个数。于是遍历给定数据，将特定数减去当前读取的数的差保存起来，如果后面的数和已保存的数相等，那么就能说明概数已经找到和它配对的数，两数相加等于特定数了。

优化的点就在于便利数据以记录特定数与各数之差一次，用各数和所记录的差比对一次，两次遍历便可解决问题，所以时间复杂度为 O(n)，进一步考虑，可将两次遍历合为一处，用一个范围 for 循环来完成（事实上用 for 循环整体效率貌似更高）。关键在于如何储存差值以使比对的时间消耗尽量小呢？在 cpp 中，我们可以使用容器 map。

具体代码如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> check_tab;
                vector<int> result;
                int cnt=0;
                for(auto i : nums){
                        if(!check_tab.count(i))
                                check_tab[target-i]=cnt;
                        else{
                                result.push_back(check_tab[i]);
                                result.push_back(cnt);
                                break;
                        }
                        ++cnt;
                }
                return result;
    }
};

这一次结果如下——

效果确实比第一次好多了。

可以看到，中间的那一次记录是本菜鸡自己尝试的优化，我想，既然相加为一个数，那么遇到比该数大的数不是可以直接跳过吗？结果——

没错，本鸡没有考虑到存在负数的情况。

虽然第三次的代码已经比第一次的好上很多了，但是还是可以做一些形式上的优化：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> check_tab;
                int cnt=0;
                for(auto i : nums){
                        if(check_tab.count(i))
                                return vector<int>{check_tab[i],cnt};
                        else
                                check_tab[target-i]=cnt;
                        ++cnt;
                }
        return vector<int>();
    }
};

主要的改进在于返回时构建 vector 对象，利用构造函数直接初始化要比先定义一个空 vector 在向其中添加数据快得多！最后的 return 语句只是语法上需要（否则会报错），实际上并不会执行到它。

最终改进后的代码运行效率大大提升——

---

通过最后的表格汇总也可以看到，随着运行时间的减少，空间需求越来越大，这也体现了牺牲空间，优化时间的说法，hhh。。。。。