题解 | 两数之和

这题的难点在于如何缩短他的时间复杂度为O(n)

如果直接使用BF（暴力）算法，会有部分数据不通过

这里可以使用哈希表法：遍历数组时将其值为键，位置i为值，传入哈希表中，

输入一个数据时，需要看目标数T与他的差是否在哈希表中，

这样每当输入一个数据，他的值和位置信息就会存储到哈希表中，直到遇到匹配的数据return为止.

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @param target int整型
     * @return int整型vector
     */
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        unordered_map<int, int> map;
        for (int i = 0; i < nums.size(); i++) {
            if(map.count(target-nums[i])){
                ans.push_back(map[target-nums[i]]);
                ans.push_back(i+1);
                return ans;
            }
            map.emplace(nums[i],i+1);
        }


        return ans;
        // write code here
    }
};