📚 数组、链表

  1. 数组

    分配一块连续的内存，每个元素只需要通过索引就可以访问，效率为O(1).数组进行增删操作时，会涉及大量片段的复制群移元素，效率为O(n)。

  2. 链表

    这时候用链表可以省去这些操作，它的移动修改操作效率为O(1)。同时也是因为这样的结构，要访问链表里的元素变得不那么简单，效率为O(n)。
    单向链表：链表 Linked List，每个元素有value 和 next，next 指向下一个元素。最后一个元素的 next 指向空 None
    循环列表：头指针为 Head, 尾指针为 Tail, Tail 的 next 指向 Head
    双向链表：有两个指针 prev 和 next可以往前走，也可以往后走

  3. 跳表
    跳表对标的是平衡树和二分查找，是一种插入/删除/搜索都是O(log n)的数据结构。


🤔 解题思路

  1. 暴力循环

  2. 双指针
    双指针，是指用两个变量在线性结构上遍历而解决的问题。双指针算法是基于暴力解法的优化。

    • 对于数组，指两个变量在数组上相向移动解决的问题
    • 对于链表，指两个变量在链表上同向移动解决的问题，也称为「快慢指针」问题
    • 左右指针夹逼

    左右指针分别指向左右两端，根据情况向中间移动。适用于两数之和，三数之和，四数之和, 盛最多水的容器这样的 LeetCode 题目，先对数组进行排序，然后左右夹逼求值。

    • 快慢指针

    不断维护一维数组的双指针来做一些事情

  3. 滑动窗口


🏫 经典题目

283.移动零(双指针 - 快慢指针)

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。必须在不复制数组的情况下原地对数组进行操作。
输入：[0,1,0,3,12]
输出: [1,3,12,0,0]
思路：for 循环双指针，i 指针指向遍历的元素，j 指针 0 元素的索引。nums[i] !== 0 时，nums[j] = nums[i]，同时让 nums[i] = 0, j++。
套路：不断维护一维数组的双指针来做一些事情
时间复杂度：n

1
2
3
4
5
6
7
8
9
10
11
12
13
var moveZeroes = function (nums) {
  let j = 0;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== 0) {
      nums[j] = nums[i];
      if (i !== j) {
        nums[i] = 0;
      }
      j++;
    }
  }
  return nums;
};


11. 盛水最多的容器（双指针 - 左右夹击）

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
输入：[1,8,6,2,5,4,8,3,7]
输出：49
题解：左右指针夹逼，每次移动短的指针，因为移动长的指针，容器的高度不会增加，宽度会减少，所以面积只会减小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const maxArea = (height) => {
  let l = 0;
  let r = height.length - 1;
  let maxArea = 0;
  while (l < r) {
    const area = Math.min(height[l], height[r]) * (r - l);
    maxArea = Math.max(maxArea, area);
    if (height[l] < height[r]) {
      l++;
    } else {
      r--;
    }
  }
  return maxArea;
};


15. 三数之和 （双指针 - 左右夹击）

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
题解：数组先排序，三指针，定住一个指针，剩下两个指针左右指针夹逼。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var threeSum = function (nums) {
  let arr = [];
  nums.sort((a, b) => a - b);
  for (let k = 0; k < nums.length - 2; k++) {
    if (nums[k] > 0) break;
    if (k > 0 && nums[k] == nums[k - 1]) continue; // 跳过重复的k值
    let i = k + 1;
    let j = nums.length - 1;

    while (i < j) {
      const sum = nums[k] + nums[i] + nums[j];
      if (sum === 0) {
        arr.push([nums[k], nums[i], nums[j]]);
        while (i < j && nums[i] === nums[++i]) {}
        while (i < j && nums[j] === nums[--j]) {}
      } else if (sum < 0) {
        while (i < j && nums[i] === nums[++i]) {}
      } else {
        while (i < j && nums[j] === nums[--j]) {}
      }
    }
  }

  return arr;
};


239. 滑动窗口的最大值(滑动窗口)

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const maxSlidingWindow = (nums, k) => {
  const q = []; // 存放优先队列的元素下标，为了取值方便
  const result = []; // 结果数组

  for (let i = 0; i < nums.length; i++) {
    // 如果队列不为空，当前元素大于队列里的其他元素，则弹出
    while (q.length && nums[i] >= nums[q[q.length - 1]]) {
      q.pop();
    }

    // 当前元素下标入栈
    q.push(i);

    // 判断当前最大值是否在窗口中，若不在则让其出队
    while (q[0] <= i - k) {
      q.shift();
    }
    // 达到窗口大小时，就向结果添加数据
    if (i >= k - 1) result.push(nums[q[0]]);
  }
  return result;
};


3. 无重复字符的最长子串(滑动窗口)

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

滑动窗口
维护一个滑动窗口，窗口内都是没有重复的字符，尽可能去扩大窗口的大小

  1. 如果当前遍历到的字符从未出现，直接扩大右边界
  2. 如果当前遍历到的字符出现过，则缩小窗口（左边索引向右移动），继续观察
  3. 重复 1，2，知道左边索引无法再移动
  4. 维护 res，更新无重复字符的最长子串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const lengthOfLongestSubstring = (s) => {
  const dict = new Map();
  let minIndex = 0, // 滑动窗口的左指针
    maxLength = 0,
    curIndex; // 表示和滑动窗口的右指针元素相同的最新的索引

  for (let i = 0; i < s.length; i++) {
    // i是滑动窗口的右指针
    curIndex = dict.get(s[i]);
    if (curIndex >= minIndex) {
      // 元素重复,将左指针移动上次出现这个字符的索引的下一位
      minIndex = curIndex + 1;
    }
    dict.set(s[i], i); // 记录字符的最新索引
    maxLength = Math.max(i + 1 - minIndex, maxLength);
  }
  return maxLength;
};