【LeetCode】1. Two Sum

链接:Two Sum

描述:在数组中找到两个数,他们相加的和等于目标,返回这两个数的索引。

思路:可以采用朴素解法,两层循环,但如果数据过多,将会导致超时。更好的办法是采用哈希表保存对应加数的索引并搜索。

解法:

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> res;
        map<int,int> pos;
        int sz = (int)numbers.size();

        for(int i=0; i<sz; i++) {
            // 搜索与当前加数对应的另一加数
            auto it = pos.find(target - numbers[i]);
            // 如果没找到,则把当前加数的索引保存起来,并继续搜索
            if(it == pos.end()) {
                pos[numbers[i]] = i;
            }
            // 找到了另一个加数
            else{
                res.push_back(it->second);
                res.push_back(i);
                break;
            }
        }
        return res;
    }
};

发表于:2014年10月26日 ,阅读量:507 ,标签:LeetCode

版权声明:若非特别注明,本站所有文章均为作者原创,转载请务必注明原文地址。