一、LeetCode 1. 两数之和

题目介绍：

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例：

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

二、解题思路

我们由浅入深，一一来进行探讨学习。

1. 使用枚举的形式，一一进行组合

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
*/
var twoSum = function(nums, target) {
  let len = nums.length;
  for (let i = 0; i< len; i++) {
    for (let j = i + 1; j < len; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j]
      }
    }
  }
};

2. 在LeetCode上提交后，看下给出的评价结果：

解题分析：

虽然提交的算法满足了题目的需求，但是执行用时、内存消耗都是不理想的。 我们看下该算法的时间复杂度和空间复杂度：

1. 最大复杂度Case:

// 符合结果的在最后两位
nums = [11,15, 2,7], target = 9

2. 最小复杂度Case:

// 符合结果的就在前两位
nums = [2,7,11,15], target = 9

我们使用枚举的形式来查询到结果，时间复杂度是趋近于O(n2)O(n^2)O(n2)的。

那我们可以实现一种时间复杂度小于O(n2)O(n^2)O(n2)的算法吗？

2. 进阶算法：一种O(n)O(n)O(n)时间复杂度的算法

我们仔细分析下题目，在数组nums中存在唯一的一个结果[m,n][m, n][m,n]，两个数的和为target。

假如我们将数组nums的值存储到一个Map对象中，存在 [m,n=target−m][m, n = target -m][m,n=target−m]的情况。

这里插播一条小知识：Map

Map是ES6中，新增加的一种数据结构，类似于对象，是键值对的集合（Hash 结构）。但是键的类型不仅仅局限于字符串。

我们来看下具体的算法实现：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    // 创建Map对象
    const map = new Map();
    const len = nums.length;
    for (let i = 0; i < len; i++) {
        // 当前值 nums[i]
        const x = target - nums[i];
        // 判断Map中是否已经存在了x
        if(map.has(x)) {
            return [map.get(x), i]
        }
        // 将当前的值存入到map中
        map.set(nums[i], i)
    }
};

在LeetCode上提交后，看下给出的评价结果：

解题分析：

Amazing! 时间复杂度大幅度降低了，从结果来看是十分符合需求的。

我们看下该算法的时间复杂度和空间复杂度：

最大复杂度Case:

// 符合结果的其中一个值在最末位，复杂度为O(n)
nums = [11,15, 2,7], target = 9

最小复杂度Case:

// 符合结果的就在前两位 O(1)
nums = [2,7,11,15], target = 9

你喜欢这个算法实现吗？手动微笑.gif

此处也可以直接使用Object对象结构，只不过判断条件需要调整为 obj[target - nums[i]] !== undefined。可以动手尝试一下呦~

三、总结

今天我们通过 LeetCode 1. 两数之和的题目，开始了正式的算法之旅。

在理解掌握算法的过程中，不是一蹴而就的，我们都可以逐步来寻求算法的最优解。

首先我们可以做到，实现题目的需求，解决问题是第一要务的；

然后在此之上，考虑如何在数据结构或者是实现思路上进行调整优化，得到更有的解决方案。

算法-从菜鸟开始，而无止境。与君共勉！