首页 > itarticle > leetcode 001 two sum

leetcode 001 two sum

admin 11月 11, 2020 0

Leetcode 001 题

Difficulty:Easy

**Tag: Map **

题目

题目原址：https://leetcode.com/problems/two-sum/#/description

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.

例子

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

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

思路

其实就是一个边建立字典边访问字典的过程：

字典的key-value 分别为
key: nums[i]
value: index

伪代码更能描述这个过程
for num in nums
    1. if target - num in dict
    2.    说明字典中存在一个元素 + num = target，返回下标
    3.将num放入dict中

代码

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