LeetCode - 数组

PS：按照代码随想录的题单顺序刷题，记录一下。

1. 基础概念

• 数组是存放在连续内存空间上的相同类型数据的集合。
• 下标从 0 开始。
• 元素地址连续。
• 插入或删除时需要移动元素位置，时间复杂度 O(n)，取元素 O(1)。

2. 二分查找

2.1 关键条件

1. 有序数组。
2. 元素不重复。

2.2 两种写法

二分查找模板比较简单，需要注意的是区间的定义（左闭右闭还是左闭右开），不要写乱了。

时间复杂度：O(logn)。

空间复杂度：O(1)。

写法一（左闭右闭）：

function fun(nums, target) {
  let left = 0, right = nums.length - 1;
  let mid;
  // 左闭右闭
  while(left <= right) {
    mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return mid;
}

写法二（左闭右开）：

function fun(nums, target) {
  let left = 0,  right = nums.length;
  let mid;
  // 左闭右开，
  while(left < right) {
    mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] > target) {
      right = mid;
    } else {
      left = mid + 1
    }
  }
  return mid;
}

2.3 二分查找

描述

LeetCode704 - 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。简单

示例1：

输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4

示例2：

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

思路

经典二分查找，一遍过。

704 - 二分查找

var search = function(nums, target) {
    let left = 0, right = nums.length - 1;
    let mid;
    while(left <= right) {
        mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
};

2.4 搜索插入位置

描述

LeetCode35 - 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。简单

示例1：

输入: nums = [1,3,5,6], target = 5
输出: 2

示例2：

输入: nums = [1,3,5,6], target = 2
输出: 1

思路

要求时间复杂度 O(log n)，很容易想到二分。

35 - 搜索插入位置

var searchInsert = function(nums, target) {
  let left = 0, right = nums.length - 1;
  let mid;
  while(left <= right) {
    mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return left;
}

2.5 在排序数组中查找元素的第一个和最后一个位置

描述

LeetCode34 - 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。中等

示例1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

思路

有序数组，时间复杂度要求 O(log n)，想到二分。目标元素有多个，返回开始位置和结束位置，则找到目标后仍需继续查找，直到结束循环。

34 - 在排序数组中查找元素的第一个和最后一个位置

var searchRange = function(nums, target) {
    // 左右索引
    let minIndex = nums.length, maxIndex = -1;
    // 先找左边索引
    let left = 0, right = nums.length - 1;
    let mid;
    while(left <= right) {
        mid = Math.floor((left + right) / 2);
        if(nums[mid] >= target) {
            if(nums[mid] === target && mid < minIndex) {
                minIndex = mid;
            }
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    if(minIndex === nums.length) {
        return [-1, -1];
    }
    // 找右边索引
    left = 0, right = nums.length - 1;
    while(left <= right) {
        mid = Math.floor((left + right) / 2);
        if(nums[mid] <= target) {
            if(nums[mid] === target && mid > maxIndex) {
                maxIndex = mid;
            }
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return [minIndex, maxIndex];
};

2.6 X 的平方根

描述

LeetCode69 - 给你一个非负整数 x ，计算并返回 x 的 算术平方根。

由于返回类型是整数，结果只保留整数部分 ，小数部分将被舍去。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5。简单

示例1：

输入：x = 4
输出：2

示例2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

思路

从 0 到 X 之间找到一个数，虽然不是数组，但也很容易想到二分。

69 - X 的平方根

var mySqrt = function(x) {
    let left = 0, right = x;
    let mid, need;
    while(left <= right) {
        mid = Math.floor((left + right) / 2);
        need = mid * mid;
        if(need === x) {
            return mid;
        } else if (need > x) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left - 1;
};

2.7 有效的完全平方数

描述

LeetCode367 - 给你一个正整数 num。如果 num 是一个完全平方数，则返回 true，否则返回 false。

完全平方数是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如 sqrt。简单

示例1：

输入：num = 16
输出：true
解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。

示例2：

输入：num = 1
输出：false
解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

思路

与 69 题类似。

367 - 有效的完全平方数

var isPerfectSquare = function(num) {
    let left = 1, right = Math.floor(num / 2) + 1;
    let mid, need;
    while(left <= right) {
        mid = Math.floor((left + right) / 2);
        need = mid * mid;
        if(need === num) {
            return true;
        } else if (need > num) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return false;
};

3. 移除元素

3.1 移除元素

描述

LeetCode27 - 给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。简单

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

• 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
• 返回 k。

示例1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]

示例2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]

思路

使用双指针，右指针指向数组尾部，左指针从前往后遍历，一旦元素等于目标值就交换元素值，右指针左移，当左指针大于右指针时结束循环。

27 - 移除元素

var removeElement = function(nums, val) {
    let left = 0, right = nums.length - 1;
    while(left <= right) {
        if(nums[left] === val) {
            nums[left] = nums[right];
            nums[right] = val;
            right--;
            continue;
        }
        left++;
    }
    return left;
};

3.2 删除排序数组中的重复项

描述

LeetCode26 - 给你一个非严格递增排列的数组 nums，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。然后返回 nums 中唯一元素的个数。简单

考虑 nums 的唯一元素的数量为 k，你需要做以下事情确保你的题解可以被通过：

• 更改数组 nums，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
• 返回 k。

示例1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]

示例2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]

思路

快慢指针，如果慢指针与快指针元素不一样，则可以赋值。

26 - 删除排序数组中的重复项

var removeDuplicates = function(nums) {
    let slow = 0, fast = 1;
    while(fast < nums.length) {
        if(nums[slow] !== nums[fast]) {
            nums[++slow] = nums[fast];
        }
        fast++;
    }
    return slow + 1;
};

3.3 移动零

描述

LeetCode283 - 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 请注意，必须在不复制数组的情况下原地对数组进行操作。简单

示例1：

输入：nums = [0,1,0,3,12]
输出：[1,3,12,0,0]

示例2：

输入：nums = [0]
输出：[0]

思路

把 0 移到末尾，换个思路，从头先把非 0 元素排好，剩下的全部置 0，快慢指针，与前面题目类似。

283 - 移动零

var moveZeroes = function(nums) {
    let slow = 0, fast = 0;
    while(fast < nums.length) {
        if(nums[fast] !== 0) {
            nums[slow++] = nums[fast];
        }
        fast++;
    }
    while(slow < nums.length) {
        nums[slow++] = 0; 
    }
};

3.4 比较含退格的字符串

描述

LeetCode844 - 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true。# 代表退格字符。简单

注意：如果对空文本输入退格字符，文本继续为空。

示例1：

输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。

示例2：

输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 ""。

思路

这题用栈比较简单，如果想空间复杂度 O(1) 可以用双指针，就是两个字符串从后往前遍历，遇到 # 就表示前一个字符需要被删除，每次找到两个字符串不会被删除的字符进行比较。

844 - 比较含退格的字符串

var backspaceCompare = function(s, t) {
    let sNum = 0, tNum = 0;
    let sIndex = s.length - 1, tIndex = t.length - 1;
    while(sIndex > -1 || tIndex > -1) {
        while(sIndex > -1) {
            if (s[sIndex] === '#') {
                sNum++;
            } else if(sNum > 0) {
                sNum--;
            } else {
                break;
            }
            sIndex--;
        }
        while(tIndex > -1) {
            if(t[tIndex] === '#') {
                tNum++;
            } else if(tNum > 0) {
                tNum--;
            } else {
                break;
            }
            tIndex--;
        }
        if(sIndex < 0 && tIndex < 0) {
            return true;
        } else if (sIndex > -1 && tIndex > -1) {
            if(s[sIndex] === t[tIndex]) {
                sIndex--;
                tIndex--;
            } else {
                return false;
            }
        } else {
            return false;
        }
    }
    return true;
};

4. 有序数组的平方

描述

LeetCode977 - 给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。简单

示例1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]

示例2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

思路

使用双指针比较两端元素绝对值大小，将大的元素的平方逆序存入数组，指针向中间移动。

977 - 有序数组的平方

var sortedSquares = function(nums) {
    let left = 0, right = nums.length - 1;
    const res = new Array(nums.length);
    for(let i = nums.length - 1; i > -1; i--) {
        if(Math.abs(nums[left]) >= Math.abs(nums[right])) {
            res[i] = nums[left] * nums[left];
            left++;
        } else {
            res[i] = nums[right] * nums[right];
            right--;
        }
    }
    return res;
};

5. 长度最小的子数组

5.1 长度最小的子数组

描述

LeetCode209 - 给定一个含有 n 个正整数的数组和一个正整数 target。找出该数组中满足其总和大于等于 target 的长度最小的子数组 [numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回 0。中等

示例1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例2：

输入：target = 4, nums = [1,4,4]
输出：1

思路

可以暴力，遍历每个下标，计算从该下标开始的符合条件的子数组，时间复杂度 O(n^2)。因为要求子数组连续，也很容易想到滑动窗口方法。

209 - 长度最小的子数组

var minSubArrayLen = function(target, nums) {
    let left = 0, right = 0;
    let res = nums.length + 1;
    let count = 0;
    while(right < nums.length) {
        // 加入窗口
        count += nums[right];
        // 缩小窗口
        while(count >= target) {
            // 更新结果
            if(right - left + 1 < res) {
                res = right - left + 1;
            }
            count -= nums[left];
            left++;
        }
        right++;
    }
    return res > nums.length ? 0 : res;
};

5.2 水果成篮

描述

LeetCode904 - 你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果种类。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

• 你只有两个篮子，并且每个篮子只能装单一类型的水果。每个篮子能够装的水果总量没有限制。
• 你可以选择任意一棵树开始采摘，你必须从每棵树（包括开始采摘的树）上恰好摘一个水果。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
• 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits，返回你可以收集的水果的最大数目。中等

示例1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例2：

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

思路

题目翻译一下就是找到连续子数组，长度最长，子数组元素只能最多两种，可以用滑动窗口，同时用 map 保存当前篮子水果，当超过两种窗口开始收缩。

904 - 水果成篮

var totalFruit = function (fruits) {
  // 记录当前篮子中的水果种类
  let map = new Map();
  let left = 0, right = 0;
  let res = 0;
  while (right < fruits.length) {
    // 窗口右移
    map.set(fruits[right], (map.get(fruits[right]) || 0) + 1);
    // 窗口收缩
    while (map.size > 2) {
      map.set(fruits[left], map.get(fruits[left]) - 1);
      if (map.get(fruits[left]) === 0) {
        map.delete(fruits[left])
      }
      left++;
    }
    // 更新res
    if (right - left + 1 > res) {
      res = right - left + 1
    }
    right++;
  }
  return res;
};

5.3 最小覆盖子串

描述

LeetCode76 - 给你一个字符串 s、一个字符串 t。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""。困难

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

思路

找最小子串，可以想到滑动窗口，当涵盖了全部字符则开始收缩。

76 - 最小覆盖子串

var minWindow = function(s, t) {
    if(s.length < t.length) return '';
    let left = 0, right = 0;
    let res = '';
    let minLength = s.length + 1;
    // 使用map保存t中字符信息
    const tMap = new Map();
    // 用于判断是否找到全部字符
    const tMapCopy = new Map();
    for(let v of t) {
        tMap.set(v, (tMap.get(v) || 0) + 1);
        tMapCopy.set(v, (tMapCopy.get(v) || 0) + 1);
    }
    // 用于保存已找到的字符
    const find = new Map();
    while(right < s.length) {
        // 是t的字符就加入find
        if(tMap.has(s[right])) {
            find.set(s[right], (find.get(s[right]) || 0) + 1);
        }
        // 还未找到全部t中字符
        if(tMapCopy.has(s[right])) {
            tMapCopy.set(s[right], tMapCopy.get(s[right]) - 1);
            if(tMapCopy.get(s[right]) === 0) {
                tMapCopy.delete(s[right])
            }
        }
        // 找到全部字符，收缩窗口
        while(tMapCopy.size === 0) {
            // 更新res
            if(right - left + 1 < minLength) {
                res = s.substring(left, right + 1);
                minLength = right - left + 1;
            }
            if(find.has(s[left])) {
                // 有多余则可以删除，继续缩小窗口，否则退出循环
                if(find.get(s[left]) > tMap.get(s[left])) {
                    find.set(s[left], find.get(s[left]) - 1);
                } else {
                    break;
                }
            }
            left++;
        }
        right++;
    }
    return res;
};

6. 螺旋矩阵Ⅱ

6.1 螺旋矩阵Ⅱ

描述

LeetCode59 - 给你一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix。中等

示例1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例2：

输入：n = 1
输出：[[1]]

思路

初始化二维数组，按顺时针方向赋值，使用两个指针控制行列位置，用一个标志位表示方向，达到临界点改变方向，注意指针变化。

59 - 螺旋矩阵Ⅱ

var generateMatrix = function(n) {
  let res = []
  for(let i = 0; i < n; i++){
    res.push([])
  }
  let row = 0, column = 0;
  let flag = 1;
  for(let i = 1; i <= n * n; i++){
    res[row][column] = i;
    switch(flag){
      case 1:
        column++;
        if(column === n || res[row][column]){
          column = column - 1;
          row++;
          flag = 2;
        }
        break;
      case 2:
        row++;
        if(row === n || res[row][column]){
          row = row - 1;
          column--;
          flag = 3;
        }
        break;
      case 3:
        column--;
        if(column === -1 || res[row][column]){
          column = column + 1;
          row--;
          flag = 4;
        }
        break;
      case 4:
        row--;
        if(row === -1 || res[row][column]){
          row = row + 1;
          column++;
          flag = 1;
        }
        break;
    }
  }
  return res
}

6.2 螺旋矩阵

描述

LeetCode54 - 给你一个 m 行 n 列的矩阵 matrix，请按照顺时针螺旋顺序，返回矩阵中的所有元素。中等

示例1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

思路

与 59 题类似，直接模拟顺时针顺序即可，用一个标志位表明方向，用双指针控制位置。

54 - 螺旋矩阵

var spiralOrder = function(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    const res = [];
    let row = 0, col = 0, direction = 1;
    // 边界
    let rowStart = 0, colStart = 0, rowEnd = m - 1, colEnd = n - 1;
    for(let i = 1; i <= m * n; i++) {
        res.push(matrix[row][col]);
        switch(direction) {
            case 1:
                col++;
                if(col > colEnd) {
                    col = colEnd;;
                    row++
                    rowStart++;
                    direction = 2;
                }
                break;
            case 2: 
                row++;
                if(row > rowEnd) {
                    row = rowEnd;
                    col--;
                    colEnd--;
                    direction = 3;
                }
                break;
            case 3:
                col--;
                if(col < colStart) {
                    col = colStart;
                    rowEnd--;
                    row--;
                    direction = 4;
                }
                break;
            case 4: 
                row--;
                if(row < rowStart) {
                    row = rowStart;
                    colStart++;
                    col++;
                    direction = 1;
                }
                break;
        }
    }
    return res;
};