Table of Contents

一、哈希

1. 两数之和

思路

使用哈希表存储每一个数据，数据为键，所对应的下表为索引
遍历数组，哈希表中某元素+当前遍历到的元素 = target 时候，即为所需答案

代码

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

二、双指针

283. 移动零

思路

设立i，j两个指针，初始时候指向第一个元素
遍历数组
1. 每当第j个元素为0时候就跳过继续遍历
2. 当第j个元素不为0时候，交换数组中第i个元素和第j个元素，然后将i向右挪动一个

题解

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    for(let i=0, j=0; j<nums.length; j++){
        if(nums[j] === 0) continue
        let value = nums[j]
        nums[j] = nums[i]
        nums[i] = value
        i++
    }
};

三、数组

53. 最大子数组和

思路

维护两个变量

sum：当前连续子数组的和
best：历史最大连续子数组和

遍历数组

每加一个数，就把它加到 sum
如果 sum 比 best 大，更新 best
如果 sum < 0 清空 sum 重新开始

题解

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let sum = 0
    let best = -99999
    for(let i=0; i<nums.length; i++){
        if(sum<0) sum = 0
        sum += nums[i]
        if(sum > best) best = sum
    }
    return best
};

56. 合并区间

思路

先按区间起点从小到大排序，保证遍历时前面的区间起点不会超过后面的
初始化空结果数组 result，以及一个索引 idx 用来指向结果中的最后一个区间
对每个区间 intervals[i]：
1. 若 result 为空，直接放进去作为起始区间。
2. 否则用当前区间与结果中最后一个区间比较：
  1. 若重叠，则更新末端，取两数组第二个数字的更大值
  2. 若不重叠，直接把当前区间推入 result，然后 idx++ 指向新的最后一个区间。

题解

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    intervals.sort((a,b) => a[0] - b[0])
    let result = []
    let idx = 0;
    for(let i=0; i<intervals.length; i++){
        if(result.length == 0) {
            result.push(intervals[i])
            continue
        }
        if(result[idx][1] >= intervals[i][0]){
            result[idx][1] = Math.max(intervals[i][1], result[idx][1])
            continue
        }
        result.push(intervals[i])
        idx++
    }
    return result
};

189. 轮转数组

思路

首先对 k 取模，应对 k 超出数组长度的情况（此时的 k 即为要轮转的步数，同时也为划分点）
将数组按照（数组长度 - k）｜ k 来切分为两部分
对两部分进行拼接并返回结果即为正确答案，此时空间复杂度为O(n)

var rotate = function(nums, k) {
    k %= nums.length;
    k = nums.length - k
    let result = []
    let result_left = nums.slice(0, k)
    let result_right = nums.slice(k, nums.length)
    result.push(...result_right, ...result_left)
    nums.splice(0, nums.length, ...result);
};

优化空间复杂度：
1. 观察可得若把数组完全反转 [0, 1, 2, 3] -> [3, 2, 1, 0]
2. 再对其以 k 为分界线进行反转即可得到预期答案，如 k = 2，[3, 2, 1, 0]->[2, 3, 0, 1]
编写原地反转代码并结合即可，此时空间复杂度为O(1)

题解

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    k %= nums.length
    reverse(nums,0, nums.length - 1)
    reverse(nums, 0, k-1)
    reverse(nums, k, nums.length - 1)
};

const reverse = (nums, l, r) => {
    for (; l < r; l++, r--) {
        let c = nums[l];
        nums[l] = nums[r];
        nums[r] = c;
    }
}

四、二叉树

94. 二叉树的中序遍历

思路

左子树 → 根节点 → 右子树

在深度遍历二叉树每个节点时，返回到当前节点时，将当前节点的

题解

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
    let result = []
    const find = (node) => {
        if (node.value === null) return
        find(node.left)
        result.push(node.val)
        find(node.right)
    }
    find(root)
    return result
};

104. 二叉树的最大深度

思路

定义当前遍历深度和最大深度
创建递归函数，用来遍历每一个节点
1. 进入新节点时，如果是空节点直接返回
2. 当前深度+1，比对当前深度和最大深度
3. 遍历左子树和右子树
4. 回到当前节点时，深度-1
返回最大深度

题解

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    let dep = 0
    let maxDep = 0
    const depth = (r) => {
        if (r === null) return
        dep++
        maxDep = Math.max(maxDep, dep)
        depth(r.left)
        dep--
        depth(r.right)
    }
    depth(root)
    return maxDep
};

226. 翻转二叉树

思路

递归遍历二叉树
每次进入节点，交换其左右节点，如果节点为空则返回

题解

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    const reverse = (r) => {
        if (r === null) return
        let test = r.right
        r.right = r.left
        r.left = test
        reverse(r.right)
        reverse(r.left)
    }
    reverse(root)
    return root
};

101. 对称二叉树

思路

首先判断是否为空二叉树
比对二叉树是否对称
1. 采用两两比较（先比较根节点的左子树和右子树）
2. 若两者皆为null则返回true
3. 若任意一者为null则返回false
4. 若二者的值不相等则返回false
5. 递归(左子树的左 vs 右子树的右)&&(左子树的右 vs 右子树的左)

题解

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if (root === null) return true
    const isMirror = (left, right) => {
        if (left === null && right === null) return true
        else if (left === null || right === null) return false
        if (left.val !== right.val) return false
        return isMirror(left.left, right.right) && isMirror(left.right, right.left)
    }
    return isMirror(root.left, root.right)
};

543. 二叉树的直径

思路

定义 max 来记录最大直径
定义递归函数来求以该点为根节点的左右子树的最大值
1. 若当前节点为空，则返回0
2. 递归计算左、右子树的深度
3. 更新最大直径 max 为左右子树深度和（若小于则不更新）
4. 返回 1 + 左右子树的最大深度

题解

/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function(root) {
    let max = 0
    const length = (n) => {
        if(n === null) return 0
        let leftLength = length(n.left)
        let rightLength = length(n.right)
        max = Math.max(max, leftLength+rightLength)
        return 1 + Math.max(leftLength, rightLength)
    }
    length(root)
    return max
};

102. 二叉树的层序遍历

思路

定义节点存储队列（先进先出）和返回结果（空数组）
如果根节点为空则直接返回空数组
遍历节点存储队列（使用while循环）：
1. 确定当前层节点数
2. 遍历当前层的节点（用for循环）
  1. 从队列拿出一个节点
  2. 读取其值放入临时数组
  3. 读取其左右节点放入节点存储队列
3. 将临时数组放入结果

题解

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    let queue = []
    let insert = []
    if (root === null) return insert
    queue.push(root)
    while (queue.length > 0){
        let size = queue.length
        let temp = []
        for (let i = 0; i < size; i++){
            let next = queue.shift()
            if (next === null) continue
            temp.push(next.val)
            queue.push(next.left)
            queue.push(next.right)
        }
        if (temp.length === 0) continue
        insert.push(temp)
    }
    return insert
};

114. 二叉树展开为链表

思路

因展开为链表后结果与二叉树先序遍历一样，那么反向遍历，然后拼接即可。等价于先访问最后一个节点，然后把链表向上拼接回去，最后根节点成为链表的头。
按反向先序遍历->从右往左遍历->n.right = prev，n.left = null，再把 prev = n

题解

/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function(root) {
    let prev = null
    const reversePreorder = (n) => {
        if (n === null) return
        reversePreorder(n.right)
        reversePreorder(n.left)
        n.right = prev
        n.left = null
        prev = n
    }
    reversePreorder(root)
};

五、字串

560. 和为 K 的子数组

思路

使用前缀和 + 哈希表来做
维护sum为从开头到当前下标 i 的元素和，result为和为 k 的子数组数量，map 键是某个前缀和，值是这个前缀和出现的次数。map.set(0,1)：表示“前缀和为 0 出现过一次（在下标 -1 的位置）”
遍历数组
1. 把它加到 sum 上
2. 看看 map 里有没有 sum - k，有的话说明存在一些先前的位置 j，使得从 j+1 到 i 的子数组和等于 k。这些位置的数量就是 map.get(sum - k)，把这个数加到 result。
3. 把当前 sum 的出现次数在 map 里加 1

题解

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    let map = new Map()
    map.set(0,1)
    let sum = 0
    let result = 0
    for(let i=0; i<nums.length; i++){
        sum += nums[i]
        if(map.has(sum-k)){
            result+=map.get(sum-k)
        }
        if(map.has(sum)){
            map.set(sum, map.get(sum)+1)
        }else{
            map.set(sum,1)
        }
    }
    return result
};