数组解题技巧

初始定义

基础算法思想

哈希映射

参考题目：

两数之和

做算法题的时候，要有这样的一种本能：当发现自己的代码里有两层循环时，先反思一下，能不能用空间换时间，把它优化成一层循环。

因为两层循环很多情况下都意味着 O(n^2) 的复杂度，这个复杂度非常容易导致你的算法超时。即便没有超时，在明明有一层遍历解法的情况下，你写了两层遍历，面试官对你的印象分会大打折扣。

空间换时间

大家记住一个结论：几乎所有的求和问题，都可以转化为 求差问题。两数之和就是一个典型的例子，通过把求和问题转化为求差问题，事情会变得更加简单。

双索引技巧

定义两个指针，确定指针的开头和结尾。

解决双指针问题三种常用思想：

左右指针：需要两个指针，一个指向开头，一个指向末尾，然后向中间遍历，知道满足条件或者两个指针相遇
快慢指针：需要两个指针，开始都指向开头，根据条件不同，快指针走得快，慢指针走得慢，直到满足条件或者快指针走到结尾
后序指针：常规指针操作是从前向后遍历，对于合并和替换类型题，防止之前的数据被覆盖，双指针需从后向前遍历

口诀：左右指针中间夹，快慢指针走到头，后序指针往回走

快慢指针

快慢指针一般都初始化指向链表的头结点 head，前进时快指针 fast 在前，慢指针 slow 在后，巧妙解决一些链表中的问题。

快慢指针也是双指针，但是两个指针从同一侧开始遍历数组，将这两个指针分别定义为快指针（fast）和慢指针（slow），两个指针以不同的策略移动，直到两个指针的值相等（或其他特殊条件）为止，如 fast 每次增长两个，slow 每次增长一个。

伪代码：

const fn = function (head) {
  if (head === null || head.next === null) return false;

  let slow = head;
  let fast = head.next;

  while (slow !== fast) {
    if (fast === null || fast.next === null) {
      return false;
    }

    slow = slow.next;
    fast = fast.next.next;
  }

  return true;
};

常见问题：

计算链表的中点：快慢指针从头节点出发，每轮迭代中，快指针向前移动两个节点，慢指针向前移动一个节点，最终当快指针到达终点的时候，慢指针刚好在中间的节点。
判断链表是否有环：如果链表中存在环，则在链表上不断前进的指针会一直在环里绕圈子，且不能知道链表是否有环。使用快慢指针，当链表中存在环时，两个指针最终会在环中相遇。
判断链表中环的起点：当我们判断出链表中存在环，并且知道了两个指针相遇的节点，我们可以让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。
求链表中环的长度：只要相遇后一个不动，另一个前进直到相遇算一下走了多少步就好了
求链表倒数第 k 个元素：先让其中一个指针向前走 k 步，接着两个指针以同样的速度一起向前进，直到前面的指针走到尽头了，则后面的指针即为倒数第 k 个元素。（严格来说应该叫先后指针而非快慢指针）

对撞指针

对撞指针是指在有序数组中，将指向最左侧的索引定义为左指针（left），最右侧的定义为右指针（right），然后从两头向中间相互迫近进行数组遍历。

对撞数组适用于 有序数组，也就是说当你遇到题目给定有序数组时，应该第一时间想到用对撞指针解题。

在数组中实际是指两个索引值，一般初始化为 left = 0 和 right = nums.length。

伪代码：

const fn = function (nums) {
  let left = 0,
    right = nums.length - 1;

  while (left <= right) {
    if (条件判断) {
      // do something
      left++;
    } else {
      // do something
      right--;
    }
  }
};

滑动窗口算法

两个指针，一前一后组成滑动窗口，并计算滑动窗口中的元素的问题。

字符串匹配问题
子数组问题

我写了一首诗，把滑动窗口算法变成了默写题

总结

只要题干或者题目描述中出现 有序 和 数组，应该先思考使用双指针解决，普通指针走不通则应该立即想到对撞指针

数组方法

sort

排序

常用代码

// 生成指定长度的数组并填充
const res = new Array(n).fill(0);

Data Structure and Algorithms Guidebook