Leetcode 第一题：Two Sum（C++实现）

1、问题描述：

给定一个整数数组，返回两个数字的索引，使它们相加的值等于一个特定的目标值。假设对于每个输入只有一种解决方案，并且您不可以两次同时使用相同的元素。

2、问题的示例：

给定nums = [2,7,11,15]， target = 9，

因为nums[0] + nums[1] = 2 + 7 = 9，返回[0,1]。

3、输入与输出：vector<int> twoSum(vector<int>& nums, int target)

{

}

完成这个成员函数解决问题。

4、思路：

这个可以使用哈希表一次搞定这个问题。当我们扫描整个数组，检查当前元素的补码是否已经存在于表中。如果存在，我们已经找到解决方案并立即返回。如果不存在就向表中插入该元素。

5、这一步提供我的打败97%的人的代码实现代码：

class Solution {

public:

    vector<int> twoSum(vector<int>& nums, int target) {

        unordered_map<int,int > map;

        for(int i=0;i<nums.size();i++)

        {

            int val=nums[i];

            auto iter=map.find(val);

            if (iter!=map.end())

            {

                vector <int >vec{iter->second,i};

                return vec;

            }

            map[target-val]=i;

        } 

    }

};

6、时间复杂度分析：

时间复杂度:O(n)我们只遍历包含nn元素的列表一次。每次查找表只花费O(1)时间。

空间复杂度:O(n)所需的额外空间取决于散列表中存储的项的数量，散列表最多存储n元素。