乐趣区

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

退出移动版