正如标题所言，在我四年的编程阅历中就没刷过一道算法题，这可能与我所编写的运用有关，算法对我而言提升不是特别大。加上我几乎都是在需求中学习，而非系统性的学习。所以像算法这种基础知识我自然就不是很熟悉。

那我为何会触摸算法呢？

我在本年暑假期间有一个面试，其时面试官想考察一下我的算法才能，而我直接明摆了和说我不行（指算法上的不行），但面试官仍是想考察一下，所以就出了道斐波那契数列作为考题。

但我究竟也触摸了 4 年的代码，虽然不刷算法，但好歹也看过许多文章和代码，斐波那契数列运用递归完成的代码也有些印象，所以很快我就写出了下面的代码作为我的答案。

function fib(n) {
  if (n <= 1) return n
  return fib(n - 1) + fib(n - 2)
}

面试官问我还有没有更好的答案，我便摇了摇头表示这 5 行不到的代码难道不是最优解？

事实上这份代码看起来很简洁，实际却是耗时最慢的解法

毫无疑问，在算法这关我必定是挂了的，不过好在项目阅历及后续的项目实践考核较为顺畅，不然结局便是回去等通知了。最后面试挨近结尾时，面试官友谊提示我加强基础知识（算法），着重各种运用结构不断更新迭代，但核算机的底层基础知识是不变的。所以在面试官的建议下，便有了本文。

好吧，我供认我是为了面试才去学算法的。

对上述代码进行优化

在介绍我是从何处学习算法以及从中学到了什么，无妨先来看看上题的最优答案是什么。

关于有触摸过算法的同学而言，不难看出时刻复杂度为 O(n)，而指数阶归于爆炸式增长，当 n 十分大时履行效果缓慢，且可能会呈现函数调用仓库溢出。

假如仔细观察一下，会发现这其间进行了十分多的重复核算，咱们无妨将设置一个 res 变量来输出一下成果

function fib(n) {
  if (n <= 1) {
    return n
  }
  const res = fib(n - 1) + fib(n - 2)
  console.log(res)
  return res
}

当 n=7 时，所输出的成果如下

一位未曾涉足算法的初学者收获

这还仅仅在 n=7 的状况下，便有这么多输出成果。而在算法中要防止的便是重复核算，这可以高效的节约履行时刻，因而无妨界说一个缓存变量，在递归时将缓存变量也传递进去，假如缓存变量中存在则阐明已核算过，直接返回成果即可。

function fib(n, mem = []) {
  if (n <= 1) {
    return n
  }
  if (mem[n]) {
    return mem[n]
  }
  const res = fib(n - 1, mem) + fib(n - 2, mem)
  console.log(res)
  mem[n] = res
  return res
}

此刻所输出的成果可以很明显的发现没有过多的重复核算，履行时刻也有明显降低。

一位未曾涉足算法的初学者收获

这便是回忆化查找，时刻复杂度被优化至 O(n)。

可这仍是免不了递归调用呈现仓库溢出的状况（如 n=10000 时）。

一位未曾涉足算法的初学者收获

从上面的解法来看，咱们都是从”从顶至底”，比方说 n=7，会先求得 n=6，n=5 的成果，然后依次类推直至得到底层 n=1 的成果。

事实上咱们可以换一种思路，先求得 n=1，n=2 的成果，然后依次类推上去，终究得到 n=6，n=7 的成果，也便是“从底至顶”，而这便是动态规划的方法。

从代码上来剖析，因而咱们可以初始化一个 dp 数组，用于存放数据状态。

function fib(n) {
  const dp = [0, 1]
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
  return dp[n]
}

终究 dp 数组的最后一个成员便是原问题的解。此刻输出 dp 数组成果。

一位未曾涉足算法的初学者收获

且由于不存在递归调用，因而你当 n=10000 时也不在会呈现仓库溢出的状况（只不过终究的成果必定超出了 JS 数值可表示规划，所以只会输出 Infinity）

关于上述代码而言，在空间复杂度上可以从 O(n) 优化到 O(1)，至于完成可以参考 空间优化，这儿便不再赘述。

我想至少从这儿你就能看出算法的魅力所在，这儿我强烈推荐 hello-algo 这本数据结构与算法入门书，我的算法之旅的起点便是从这本书开端，同时激发起我对算法的爱好。

两数之和

所以在看完了这本算法书后，我便打开了大名鼎鼎的刷题网站 LeetCode，同时打开了究极经典标题的两数之和。

有人相爱，有人夜里开车看海，有人 leetcode 第一题都做不出来。

题干：

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

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

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

以下代码将会选用 JavaScript 代码作为演示。

暴力枚举

我初次触摸该题也只会暴力解法，遇事不决，暴力解决。也很验证了那句话：不管多久曩昔，我首先仍是想到两个 for。

var twoSum = function (nums, target) {
  const n = nums.length
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (nums[i] + nums[j] === target && i !== j) {
        return [i, j]
      }
    }
  }
}

当然针对上述 for 循环优化部分，比如说让 j = i + 1 ，这样就可以有用防止重复数字的循环以及 i ≠ j 的判别。由于用到了两次循环，很显然时刻复杂度为 O(n)，并不高效。

哈希表

咱们无妨将每个数字通过 hash 表缓存起来，将值 nums[i] 作为 key，将 i 作为 value。由于标题的条件则是 x + y = target，也便是 target - x = y，这样判别的条件就可以由 nums[i]+ nums[j] === target 变为 map.has(target - nums[i]) 。假如 map 表中有 y 索引，那么显然 target - nums[i] = y，取出 y 的索引以及当时 i 索引就可以得到答案。代码如下

var twoSum = function (nums, target) {
  const map = new Map()
  for (let i = 0; i < nums.length; i++) {
    if (map.has(target - nums[i])) {
      return [map.get(target - nums[i]), i]
    }
    map.set(nums[i], i)
  }
}

而这样由于只有一次循环，时刻复杂度为 O(N)。

双指针算法(特殊状况)

假如理想状况下，标题所给定的 nums 是有序的状况，那么就可以考虑运用双指针解法。先说原理，假定给定的 nums 为 [2,3,5,6,8]，而目标的解为 9。在上面的做法中都是从索引 0 开端枚举，也便是 2,3,5…依次类推，假如没找到与 2 相加的元素则从 3 开端 3,5,6…依次类推。

此刻咱们无妨从最小的数和最大的数开端，在这个比如中也便是 2 和 8，很显然 2 + 8 > 9，阐明什么？阐明 8 和中心所稀有都大于 9 即 3+8 ，5+8 必定都大于 9，所以 8 的下标必然不是终究成果，那么咱们就可以把 8 扫除，从 [2,3,5,6] 中找出成果，同样的从最小和最大的数开端，2 + 6 < 9 ，这又阐明什么？阐明 2 和中心这些数相加必定都下雨 9 即 2+3，2+5 必定都小于 9，因而 2 也应该扫除，然后从 [3,5,6] 中找出成果。就这样依次类推，直到找到终究两个数 3 + 6 = 9，返回 3 与 6 的下标即可。

由于此解法相当于有两个坐标(指针)不断地向中心移动，因而这种解法也叫双指针算法。当然，要运用该方法的前提是输入的数组有序，不然无法运用。

用代码的方法来完成：

  1. 界说两个坐标(指针)别离指向数组成员最左面与最右边，命名为 left 与 right。
  2. 运用 while 循环，循环条件为 left < right。
  3. 判别 nums[left] + nums[right] 与 target 的大小关系，假如相等则阐明找到目标(答案)，假如大于则 右指针减 1 right—-，小于则左指针加 1 left++。
function twoSum(nums, target) {
  let left = 0
  let right = nums.length - 1
  while (left < right) {
    const sum = nums[left] + nums[right]
    if (sum === target) {
      return [left, right]
    }
    if (sum > target) {
      right--
    } else if (sum < target) {
      left++
    }
  }
}

针对上述两道算法题浅浅的做个共享，究竟我还仅仅一名初入算法的小白。对我而言，我的算法刷题之旅还有很长的一段时刻。且看样子这条路可能不会太平整。

算法对我有用吗？

在我刷算法之前，我在网上看到宣扬算法无用论的人，也能看到学算法却不知怎么运用的人。

这也不由让我考虑 ，算法对我所开发的运用是否真的有用呢？

在我的开发过程中，往往面临着各种功用需求，而一般状况下我会以尽可能快的速度去完成该功用，至于说这个功用耗时 1ms，仍是 100 ms，并不在乎。由于对我来说，这种微小的速度改变并不会被感知到，或者说绝大多数状况下，处理的数据规划都处在 n = 1 的状况下，此刻咱们还会在意 n 大仍是 2ⁿ 大吗？

但假如说到了用户感知到卡顿的状况下，那么此刻才会重视性能优化，不然，过度的优化可能会成为一种徒劳的尽力。

或许正是由于我都没有用到算法解决实际问题的阅历，所以很难说服自己算法对我的工作有多大协助。但不可否认的是，算法对我当时而言是一种思维上的拓展。让我意识到一道（实际）问题的解法一般不只有一种，怎么规划规划出一个高效的解决方案才是值得咱们考虑的地方。

结语

借 MIT 教授 Erik Demaine 的一句话

If you want to become a good programmer, you can spend 10 years programming, or spend 2 years programming and learning algorithms.

假如你想成为一名优异的程序员，你可以花 10 年时刻编程，或者花 2 年时刻编程和学习算法。

这或许便是学习算法的真实含义。

参考文章

初探动态规划

学习算法重要吗?