从零开始刷 LeetCode - 数组简单题常见技巧

535 阅读2分钟

最近在准备找工作,刷了 LeetCode 一百多题,还在入门阶段。在学习新的解题技巧的同时,准备写一个系列总结归纳自己碰到过的刷题套路和思考,作为对自己学习过程的记录。

由于自己主要找前端开发,并且对 JS 比较熟悉,刷题语言采用 JS。

目前笔记结构还比较混乱,会随着刷题进程不断完善。

全系列文章也可访问这里

Arrays 数组

常需要遍历。下述方法也多适用于需要遍历的字符串有关问题。

for 循环

每循环一层时间复杂度便增加一个量级。 技巧:使用Hashmap,查找时间复杂度为 O(1),占用 O(n) 空间

例: (Two Sum) [leetcode.com/problems/tw…]

var twoSum = function (nums, target) {
  let record = new Map();

  for (const [index, num] of nums.entries()) {
    let compliment = target - num;

    // if found the pair
    if (record.has(compliment)) { // 如果找到了 compliment (说明之前存过),则返回两个坐标
      return [record.get(compliment), index];
    }
    record.set(num, index); // 如果没找到,则记录当前数的位置,以便之后查找
  }

};

双指针

使用两个指针对数组进行遍历。 时间复杂度为 O(n)。 通常需要一个判断条件来决定如何移动指针。

常见条件:

  • 升序排序数组,可根据目标值与当前值大小决定,小于目标值则左指针右移,反之则右指针左移。
  • 可能对目标值的影响

使用场景

  • 回文字符子串
  • 找一对数,尤其数组排好序后
    • 如果是找更多的数可以拆解成一个数加一对数
    • 若数组未排序,在不损失时间复杂度的情况下也可以考虑将数组排序