0001 Two Sum

• 
• C++

问题概述

解题思路

Solution 1: 两层循环

• Array
• Time: O(n×n)
• Space: O(n)

class Solution
{
public:
    std::vector<int> twoSum(std::vector<int>&nums, int target)
    {
        std::vector<int> Ans;
        for (int i = 0; i < nums.size() - 1; ++i)
        {
            for (int j = i + 1; j < nums.size(); ++j)
            {
                if (nums[i] + nums[j] == target)
                {
                    Ans.push_back(i);
                    Ans.push_back(j);
                    return Ans;
                }
            }
        }
        return Ans;
    }
};

1. for loop中的++i和i++
2. ++i是先改变i的值，而i++是先使用i值然后再改变它的值；i++输出结果是1，而++i输出结果是2。
3. 对于for loop，++i 和 i++的结果是一样的，都要等代码块执行完毕才能执行语句，但是性能是不同的。
4. 在大量数据的时候++i的性能要比i++的性能好原因：i++由于是在使用当前值之后再+1，所以需要一个临时的变量来转存。而++i则是在直接+1，省去了对内存的操作的环节，相对而言能够提高性能。

Solution 2: Hash Map

• Hash Table
• Time: O(n)

• Space: O(n)

• 哈希表

• 哈希表就是在关键字和存储位置之间建立对应关系，使得元素的查找可以以O(1)的效率进行， 其中关键字和存储位置之间是通过散列函数建立关系，记为\(Loc(i) = Hash(keyi)\)。

参考：

• std::unordered_map - cppreference.com

• 一文看懂使用C++ STL 中的哈希表 - 知乎 (zhihu.com)

• 头文件

• C++ #include<unordered_map>

• 声明

• ```c++ std::unordered_map var_name;

  std::unordered_map hashTable;