前言

掘金团队号上线，助你 Offer 临门！ 点击 查看详情

题目描述

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

方法1：（暴力法）

思路：两重循环，第一重指向第i个的时候，第二重依次遍历i后边的所有，相加一起看是否等于target，若等于则返回。

伪代码

funtion twoSum(nums,target):
  for i ← 0 to (nums.length - 1):
    for j ← (i + 1) to (nums.length - 1):
      if target == nums[i] + nums[j]:
        return [i,j];

算法复杂度分析

• 时间复杂度

1. 时间复杂度：O(N^2) ,其中 N是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次.
2. 空间复杂度：O(1)。

执行结果

方法2：（借用哈希表）

1. 首先使用哈希表将数组的下标和值进行一一对应。
2. 遍历数组中的每一个元素，使用目标值target减去被遍历的元素并将结果赋值给anotherNum变量。
3. 如果哈希表中存在anotherNum这个键，并且这个变量对应的值即下标，与正在被遍历的元素的下标不同，则将被遍历元素的下标和anotherNum元素的下标进行返回。

伪代码

function twoSum(nums,target):
  result = [];  //存储返回结果的数组
  map = new Map();   //此处实例化一个HashMap对象
  for j ← 0 to (nums.length - 1):
    map.set(nums[j],j);    //将数组中的所有元素的值和下标存储到名为map的HashMap中
  for i ← 0 to (num.length - 1):
    anotherNum = target - nums[i];
    // 如果map中有anotherNum这个元素并且下标不等于i,将i和anotherNum的下标存储到结果数组中，并返回
    break;
  return result;

算法复杂度分析

• 时间复杂度: O(N), 其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 O(1) 地寻找 target - x。
• 空间复杂度: O(N), 其中 NN 是数组中的元素数量。主要为哈希表的开销。