HelloKenLee

Leetcode 1. Two Sum 解题报告

Posted on By KenLee

题目信息

题目: 1. Two Sum
难度: Easy
正确率: 33.65%
问题描述:

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:

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

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

问题分析

  该问题的意思是,给出一个数组和一个目标,要求求出数组中的两个数的下标,使得这两个数相加为目标。

解题思路

  简单的哈希题目,把所有数组中的数通过哈希表存其下标,然后对数组中的每一个数nums[i],求哈希表中key=target-nums[i]的值即为所求的下标。

结果分析

  • 时间复杂度: $ O(N) $。
  • 空间复杂度: $ O(N) $。
  • 通过时间: 24 ms
  • 击败: 50.90%

源代码

//T(n)=2n?
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> hashTable;
        // build the hash table 
        for(int i=0;i<nums.size();++i){
            hashTable.insert(pair<int,int>(nums[i],i+1));
        }
        //for each nums[i] in array, search the target-nums[i] is in hash table(aka. is in array), if is, return the answer.
        for(int i=0;i<nums.size();++i){
            if(hashTable[target-nums[i]]!=0 && hashTable[target-nums[i]]!=i+1){
                vector<int> re;
                re.push_back(min(i+1,hashTable[target-nums[i]]));
                re.push_back(max(i+1,hashTable[target-nums[i]]));
                return re;
            }
        }
    }
};