【面试】leetcode一题多解之towSum

这是leetcode面试刷题一题多解系列的第一篇，跟大家聊下我写这个系列的初衷，作为前端开发要不要学习或者面试算法这个话题争论已久，各有说辞，在这我不做评判，只从我个人前端从业经验出发，谈谈我对算法学习的一点看法：

• 初入前端的开发者可能会和算法比较远，重点在页面的开发和后端的交互上，但是算法还是可以帮助你更好的组织数据结构，提高代码的效率最终提升页面的响应速度。
• 有一定经验的前端开发，可能会帮助团队的小伙伴解决一些疑难问题，而很多问题都需要你对框架和库有较深入的理解，可能会涉及到一些算法相关的知识。
• 如果对某一些前端细分领域感兴趣的同学比如图形处理、动画效果等，算法可能会在一些复杂问题的处理上提供很大的帮助。

最后在这越来越卷的形势下，前端面试对于算法的要求也越来越多，所以前端对于算法的学习上，不管是为了更有效的解决问题还是去做底层的框架库，亦或者就是为了面试高薪，都越来越有必要学习了。

这个系列是一题多解系列，每一道题我都会给出两种或两种以上的方法去解决，目的不仅仅是为了优化，更是为了拓展思维，给大家提供各种不同解决问题的思路，可能帮助会更大些。

题目

今天跟大家一起看一道经典的 leetcode 算法题，两数之和。

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

题解1---暴力遍历

这是最简单也是最直接的一种思路，就是两层循环遍历求和，如果等于 target，则返回结果，时间复杂度是 O(n^2),空间复杂度 O(1)。

const twoSum = function (nums, target) {
    for (let i = 0, len = nums.length - 1; i < len - 1; i++) {
        for (let j = i + 1; j < len; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j]
            }
        }
    }
    return [];
};

题解2---哈希缓存

从题解可以看到第一层遍历我们其实无法避免，而第二层的遍历目的是找到 target - x, 如果我们把所有遍历过的数据存储在哈希表里，当我们需要去查找的时候，直接去取就行了，这样就从 O(N) 的复杂度减到了 O(1)。

var twoSum = function(nums, target) {
  const map = new Map();
  for(let i = 0, len = nums.length; i < len; i++) {
    if(map.has(target-nums[i])) {
      // 如果map里面有我们需要找的值，那么直接返回就可以了
      return [i, map.get(target-nums[i])];
    }else {
      // 如果没有找到，那么将这个数存起来，遍历继续
      map.set(nums[i], i);
    }
  }
  return [];
}; 

这是一个经典的以空间换时间的思想，利用哈希表进行缓存，从而减少遍历的查询次数，这个思路非常常见,如果后面我们遇到遍历的时候，可以想一想能不能在遍历的过程当中，存储一些信息，而这些信息会在后续的操作过程中有用，那么通常是能够降低时间复杂度的，但是因为增加的hash的存储，所以通常空间复杂度会提升。

题解3---双指针法

有些情况下数据是有某种特点的，我们可以利用这个特点进行算法的编写，会有效很多，虽然这个例子数据自身没有特点，但是我们可以先进行排序，创造一个特殊的序列，在一个有序的数组中就可以用双指针法进行查找。

var twoSum = function(nums, target) {    
  // 我们需要记录原始数组中，每个元素的位置
  // 在这里改变了原始数据，这是另外一个话题
  nums = nums.map((value, index) => {
    return { value, index };
  });
  // 对数组进行排序，O(logN)
  nums.sort((a, b) => a.value - b.value);
  // 数组左右各一个指针i和j
  let i = 0,j = nums.length - 1;
  while (i < j) {
    // 因为是有序的，可以根据sum（arr[i] + arr[j]）与target的大小进行比较，
    // 如果sum大于target，sum的值要减少，j向左移，小于target，sum要增加，i向右移动，相等则返回结果，
    // 循环结束返回[]
    const sum = nums[i]["value"] + nums[j]["value"];
    if (sum === target) {
      return [nums[i]["index"], nums[j]["index"]];
    } else if (sum < target) {
      i++;
    } else {
      j--;
    }
  }
  return [];
};

上面代码先进行排序，然后就可以在有序的数组上利用双指针对序列进行查找，利用数据自身特点进行算法的编写在后续的算法系列中经常会遇见。时间复杂度为 O(NlogN),空间复杂度为 O(1)。

今天用了三种方法对 twoSum 进行了求解，除了暴力解法，主要是进行数据缓存，用空间换时间的思想，还有就是利用数据自身特点进行算法设计，很多情况，数组有序了，对其进行的查找复杂度都比较低。