题目链接

点击查看【music163】

题目描述

给定一个整数数组nums和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

示例

示例1：

输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

提示

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109

  • 只会存在一个有效答案

    思路

    思路1：暴力破解

    暴力法，不多解释。

    思路2：哈希表

    遍历数组，对每一个元素x，在map中找另一个数字target-x，如果找到了，直接返回 2 个数字的下标即可。如果找不到，就把这个数字存入map中，等待另一个数字的匹配

    题解

    1. class Solution {
    2.  public:
    3.   vector<int> twoSum(vector<int>& nums, int target) {
    4.       unordered_map<int, int> m;
    5.       // unordered_map内部实现了哈希表，查找速度快，但是无序
    6.       // map内部实现了红黑树，是有序的
    7.       for (int i = 0; i < nums.size(); ++i) {
    8.           auto it = m.find(target - nums[i]);
    9.           if (it != m.end()) {
    10.               return {it->second, i};
    11.           }
    12.           m[nums[i]] = i;
    13.       }
    14.       return {};
    15.   }
    16. };

    复杂度分析

  • 时间复杂度：0001-两数之和 - 图1，对于每个元素我们的查找时间为0001-两数之和 - 图2

  • 空间复杂度：0001-两数之和 - 图3，主要为哈希表的开销。