001. 两数之和 | Leetcode题解

苏南

发布于 2020-12-16 14:36:27

7310

发布于 2020-12-16 14:36:27

文章被收录于专栏：漫画前端

点击上方“蓝色字体”，选择“设为星标”

每天复习一道面试题，轻松拿大厂Offer~

题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

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

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

难度：

难度：简单
支持语言：JavaScript、Java、Python

复杂度分析

时间复杂度：

O(N)

空间复杂度：

O(N)

思路

最容易想到的就是暴力枚举，我们可以利用两层 for 循环来遍历每个元素，并查找满足条件的目标元素。不过这样时间复杂度为 O(N^2)，空间复杂度为 O(1)，时间复杂度较高，我们要想办法进行优化。
这里我们可以增加一个 Map 记录已经遍历过的数字及其对应的索引值。这样当遍历一个新数字的时候就去 Map 里查询 target 与该数的差值是否已经在前面的数字中出现过。如果出现过，就找到了答案，就不必再往下继续执行了。
利用数组存储差值的索引位来减少一次遍历，降低时间复杂度为O(n);
用 hashMap 存储遍历过的元素和对应的索引。
每遍历一个元素，看看 hashMap 中是否存在满足要求的目标数字。
所有事情在一次遍历中完成（用了空间换取时间）。

关键点

求和转换为求差
借助 Map 结构将数组中每个元素及其索引相互对应
以空间换时间，将查找时间从 O(N) 降低到 O(1)

代码

语言支持：JavaScript

/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：前端中文网是以前端进阶资源教程分享为主的专业网站，包括：前端、大厂面试题、typescript教程、程序人生、React.js
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = function (nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const diff = target - nums[i];
    if (map.has(diff)) {
      return [map.get(diff), i];
    }
    map.set(nums[i], i);
  }
};

/**
 * @作者：xiao_ben_zhu
 * @链接：https://leetcode-cn.com/problems/two-sum/solution/qing-xi-de-bian-liang-ming-ming-bang-zhu-ji-yi-bu-/
 */

const twoSum = (nums, target) => {
  const prevNums = {};                    // 存储出现过的数字，和对应的索引

  for (let i = 0; i < nums.length; i++) { // 遍历元素
    const curNum = nums[i];               // 当前元素
    const targetNum = target - curNum;    // 满足要求的目标元素
    const targetNumIndex = prevNums[targetNum]; // 在prevNums中获取目标元素的索引
    if (targetNumIndex !== undefined) {   // 如果存在，直接返回 [目标元素的索引,当前索引]
      return [targetNumIndex, i];
    } else {                              // 如果不存在，说明之前没出现过目标元素
      prevNums[curNum] = i;               // 存入当前的元素和对应的索引
    }
  }
}

语言支持：Java

/**
*  @作者：LeetCode-Solution
*  @链接：https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-solution/
*/
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

/**
*  @作者：guanpengchn
*  @链接：https://leetcode-cn.com/problems/two-sum/solution/jie-suan-fa-1-liang-shu-zhi-he-by-guanpengchn/
*/
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i< nums.length; i++) {
            if(map.containsKey(target - nums[i])) {
                return new int[] {map.get(target-nums[i]),i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

语言支持：Python

/**
 * @作者：lao-la-rou-yue-jiao-yue-xiang
 * @链接：https://leetcode-cn.com/problems/two-sum/solution/xiao-bai-pythonji-chong-jie-fa-by-lao-la-rou-yue-j/
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
def twoSum(nums, target):
    lens = len(nums)
    j=-1
    for i in range(lens):
        if (target - nums[i]) in nums:
            if (nums.count(target - nums[i]) == 1)&(target - nums[i] == nums[i]):#如果num2=num1,且nums中只出现了一次，说明找到是num1本身。
                continue
            else:
                j = nums.index(target - nums[i],i+1) #index(x,i+1)是从num1后的序列后找num2
                break
    if j>0:
        return [i,j]
    else:
        return []