lintcode-两数之和-56

给一个整数数组，找到两个数使得他们的和等于一个给定的数target。

你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是1到n，不是以0开头。

样例

numbers=[2, 7, 11, 15],  target=9

return [1, 2]

class Solution {
public:
   
    map<int,int> vis;

    vector<int> twoSum(vector<int> &nums, int target) {
        if(nums.empty())
            return nums;
       
        vector<int> ret(2);
        int n=nums.size();
        
        for(int i=0;i<n;++i){
                vis[target-nums[i]]=i;    
        }
        for(int i=0;i<n;++i)
            if(vis.count(nums[i])){
                ret[0]=min(i,vis[nums[i]])+1;
                ret[1]=max(i,vis[nums[i]])+1;
                if(ret[0]!=ret[1])
                    return ret;
            }
        return ret;
    }
};

阅读更多