题目描述

给定一个整数数组 nums和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

样例

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

数据范围

无

算法1

(暴力)O(n^2)

• 两重循环
  

时间复杂度

• 每个位置扫描其余n-1个位置,所以时间复杂度为_O(n^2)_

空间复杂度

• O(1)

C++代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for(int i = 0;i < n;i ++){
            for(int j = i + 1;j < n;j ++){
                if(nums[i] + nums[j] == target) 
                {
                    return {i,j};
                    break;
                }
            }
        }
        return {0,0};
    }
};

算法2

(哈希表)O(n)

• 将数组元素作为Key,数组下标作为Value,遍历n次
• 令f=目标值(targe)减去当前数组元素(nums[i])
• 判断f是否在哈希表中
• 如果在,则返回改哈希表的Value和当前遍历元素下标i
• 如果不在,就以nums[i]为Key,以i为Value存入哈希表中,进入下一循环元素判断

时间复杂度：

遍历为n的列表1次,find()函数复杂度_O(1)总的复杂度为_O(n)

空间复杂度

所需的额外空间取决于哈希表中存储的元素数量,该表最多需要存储n个元素

C++代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        unordered_map<int,int> mp;
        for(int i = 0;i < n;i ++){
            int f = target - nums[i];
            unordered_map<int,int>::const_iterator got = mp.find(f);
            if(mp.find(f) != mp.end())
                return {got->second,i};
            mp[nums[i]] = i;
        }
        return {0,0};
    }
};

相关语法小案例

// unordered_map::find
#include <iostream>
#include <string>
#include <unordered_map>     Edit & Run
    int main ()
{
  std::unordered_map<std::string,double> mymap = {
     {"mom",5.4},
     {"dad",6.1},
     {"bro",5.9} };
    std::string input;
  std::cout << "who? ";
  getline (std::cin,input);
    std::unordered_map<std::string,double>::const_iterator got = mymap.find (input);
    if ( got == mymap.end() )
    std::cout << "not found";
  else
    std::cout << got->first << " is " << got->second;
    std::cout << std::endl;
    return 0;
}

Possible output:
who? dad
dad is 6.1