乐趣区

关于前端:面试leetcode一题多解之towSum

jiezi

这是 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 进行了求解，除了暴力解法，次要是进行数据缓存，用空间换工夫的思维，还有就是利用数据本身特点进行算法设计，很多状况，数组有序了，对其进行的查找复杂度都比拟低。

退出移动版