【LeetCode】1. 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].


思路:

  • 先用 map 存储每个元素对应的原始下标,方便后续查找特定元素。
  • 从头开始查找符合条件的结果,用 target 减去 nums[i] ,得到两数之差 t ,在 map 中寻找是否存在 t 且元素 t 的索引不等于 i ,若是则为最终结果,否则继续查找 nums[i+1] 。


代码实现:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> hm;
        for(int i=0;i<nums.size();i++){
            hm.insert(pair<int,int>(nums[i],i));
        }
        
        for(int i=0;i<nums.size();++i){
            int t = target-nums[i];
            if(hm.count(t)&&hm[t]!=i){
                return {i,hm[t]};
            }
        }
    }
};


 
comments powered by Disqus