Two Sum 两数之和等于一个输入的数

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

要返回数组中两个数的索引,这两个数的和等于输入的数.最简单的两层for循环可定不能满足要求.考虑优化时间复杂度,可尝试牺牲时间复杂度. stack?queue?vector?还是hash_map.stack,queue,vector查找都是O(n),hash_map为O(1).接下来尝试用hash_map解决问题.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int>res;
        if(nums.size() < 1)
            return res;
        map<int,int> hashInt;
        for (int i = 0;i<nums.size();i++)
            hashInt[nums[i]] = i;
        for (int i = 0;i < nums.size();i++)
        {
            int findInt = target - nums[i];
            if (hashInt.find(findInt)!= hashInt.end() && hashInt[findInt] != i) 
            {
                if (hashInt[findInt] < i)
                {
                    res.push_back(hashInt[findInt]);
                    res.push_back(i);
                }
                else
                {
                    res.push_back(i);
                    res.push_back(hashInt[findInt]);
                }
                break;
            }
        }
        return res;
    }
};
 
comments powered by Disqus