1. Two Sum

发表于 更新于 分类于
Given an array of integers, return indices of the two numbers such that they add up to a specific target.

Two Sum

Problem

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:

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

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

解法

首先肯定是要遍历整个数组，遍历每一个元素的时候，必须使用某一种数据结构记录下当前已经遍历过的元素，这种数据结构必须是查询方便的，自然是map/hashmap。

然后考虑具体要存放什么，我们要找的是和target相差num[i]的元素，自然key应该设置成target-num[i],value则存放当前元素的index，方便最后输出。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <vector>
#include <map>
#include <iostream>
#include <string>
#include <sstream>

using std::cin;
using std::cout;
using std::endl;
using std::getline;
using std::map;
using std::string;
using std::stringstream;
using std::to_string;
using std::vector;

class Solution
{
public:
    vector<int> twoSum(vector<int> &nums, int target)
    {
        map<int, int> remainval_index_map;
        vector<int> result;
        for (int i = 0; i < nums.size(); i++)
        {
            if (remainval_index_map.find(nums[i]) != remainval_index_map.end())
            {
                result.push_back(remainval_index_map[nums[i]]);
                result.push_back(i);
                break;
            }
            remainval_index_map[target - nums[i]] = i;
        }
        return result;
    }
};