leetcode 1. Two Sum

Posted on | Edited on | In

题目

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.

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

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

题解

使用hash, hash[i]表示i这个数字所在的索引是hash[i], 当在处理第j个节点时，查找hash[target - nums[j]] 是否存在，如果存在则得到解，返回。复杂度o(nlogn)

注意

  1. 如果使用排序，然后头尾指针遍历，因为需要返回的是索引值，若单纯建立一个hash记录每个元素的下标，会出现数组中有相同元素的时候，不好解决。 所以需要建立一个数据结构，包括该数的值和索引，然后在对数据结构排序。
  2. 如果暴力枚举i，j则复杂度为\(o(n^2)\), 会超时。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> hh;
        for(int i = 0; i < nums.size(); i++)
        {
            int tmp = target - nums[i];
            if(hh.count(tmp))
            {
                vector<int> res;
                res.push_back(hh[tmp]);
                res.push_back(i);
                return res;
            }
            else
            {
                hh[nums[i]] = i;
            }
        }
    }
};