题解 | #两数之和#

1.暴力破解

class Solution {
public:
    /**
     * 
     * @param numbers int整型vector 
     * @param target int整型 
     * @return int整型vector
     */
    vector<int> twoSum(vector<int>& numbers, int target) {
        // write code here
        vector<int> res;
        for(int i = 0;i < numbers.size(); ++i)
        {
            for(int j = i + 1;j < numbers.size(); ++j)
            {
                if(numbers[i] + numbers[j] == target)
                {
                    res.push_back(i + 1);
                    res.push_back(j + 1);
                    return res;
                }
            }
        }
        return res;
    }
};

2.优化方法
使用哈希表存储值与下标，节省寻找第二个数字的时间

class Solution {
public:
    /**
     * 
     * @param numbers int整型vector 
     * @param target int整型 
     * @return int整型vector
     */
    vector<int> twoSum(vector<int>& numbers, int target) {
        // write code here
        unordered_map<int, int>  map;
        for(int i = 0;i < numbers.size(); ++i)
        {
            auto it = map.find(target - numbers[i]);
            if(it != map.end())
                return {it->second + 1, i + 1};
            map[numbers[i]] = i;
        }

        return {};
    }
};