【代码随想录】数组刷题

数组方法总结：

• 二分法：前提是数组必须有序
• 双指针法：通过一个快指针和慢指针在一个 for 循环下完成两个 for 循环的工作
• 滑动窗口：根据当前子序列和大小的情况，不断调节子序列的起始位置
• 模拟行为：如螺旋矩阵，根据题目要求写代码

Java 中 Arrays 工具类常用 API：

int[] arr = new int[] { 1, 2, 3, 4 };

// 数组打印 (调试时方便)
Arrays.toString(arr); // [1, 2, 3, 4]

// 数组排序
Arrays.toString(arr); 

// 二分搜索 (数组必须有序)
Arrays.binarySearch(arr, 2); 

// 数组复制 (左闭右开)
int[] newArr = Arrays.copyOfRange(arr, 0, arr.length);

// 比较两个数组
Arrays.equals(arr, newArr);

// 数组全部元素赋值
Arrays.fill(arr, -1);

// 快速生成 List
List<Integer> list1 = Arrays.asList(1, 2, 3);
List<Integer> list2 = List.of(1, 2, 3);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

二分

二分查找*

题目：704. 二分查找

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

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

使用二分的前提：数组有序。

Java 源码二分：适合用于找单个值

public int search(int[] nums, int target) {
	int l = 0, r = nums.length - 1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (nums[mid] < target) l = mid + 1;
		else if (nums[mid] > target) r = mid - 1;
		else return mid;
	}
	return - 1;
}
1
2
3
4
5
6
7
8
9
10

y 总模板 1：可用于找左边界

public int search(int[] nums, int target) {
	int l = 0, r = nums.length - 1;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (nums[mid] >= target) r = mid;
		else l = mid + 1;
	}
	if (nums[l] == target) return l;
	return - 1;
}
1
2
3
4
5
6
7
8
9
10

y 总模板 2：可用于找右边界

public int search(int[] nums, int target) {
	int l = 0, r = nums.length - 1;
	while (l < r) {
		int mid = (l + r + 1) >> 1;
		if (nums[mid] <= target) l = mid;
		else r = mid - 1; 
	}
	if (nums[l] == target) return l;
	return -1;
}
1
2
3
4
5
6
7
8
9
10

搜索插入位置

题目：35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(logn) 的算法。

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

Java 源码二分：

public int searchInsert(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (nums[mid] > target) r = mid - 1;
        else if (nums[mid] < target) l = mid + 1; 
        else return mid;
    }
    return l;
}
1
2
3
4
5
6
7
8
9
10

y 总模板：

public int searchInsert(int[] nums, int target) {
	int l = 0, r = nums.length - 1;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (nums[mid] >= target) r = mid;
		else l = mid + 1;
	}
	if (nums[l] < target) return l + 1;
	return l;
}
1
2
3
4
5
6
7
8
9
10

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

题目：34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

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

二分找左边界 + 二分找右边界：

public int[] searchRange(int[] nums, int target) {
	if (nums.length == 0) return new int[] { -1, -1 };
	// 二分找左边界 - y总模板1
	int l = 0, r = nums.length - 1;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (nums[mid] >= target) r = mid;
		else l = mid + 1;
	}
	if (nums[l] != target) return new int[] { -1, -1 };
	int lb = l;
	// 二分找右边界 - y总模板2
	l = 0; r = nums.length - 1;
	while (l < r) {
		int mid = (l + r + 1) >> 1;
		if (nums[mid] <= target) l = mid;
		else r = mid - 1;
	}
	int rb = l;
	return new int[] { lb, rb };
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

其他思路：二分找到一个满足条件的值后，往左右扩散搜索边界（最坏可能是 O(n)）

x 的平方根

题目：69. x 的平方根 - 力扣（LeetCode）

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

输入：x = 4
输出：2
1
2

浮点数二分：可以输出小数点后的数字（情况没有整数二分那么复杂，写起来简单）

public int mySqrt(int x) {
	double l = 1, r = x;
	while (r - l > 1e-6) { // 设置一个精度
		double mid = (l + r) / 2;
		if (mid * mid <= x) l = mid;
		else r = mid;
	}
	return (int) r;
}
1
2
3
4
5
6
7
8
9

整数二分：使用 x / mid 防溢出

public int mySqrt(int x) {
	int l = 1, r = x;
	while (l <= r) {
		int mid = l + (r - l) / 2;
		if (mid < x / mid) l = mid + 1;
		else if (mid > x / mid) r = mid - 1;
		else return mid;
	}
	return r;
}
1
2
3
4
5
6
7
8
9
10

有效的完全平方数

题目：367. 有效的完全平方数 - 力扣（LeetCode）

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

输入：num = 16
输出：true
1
2

Java 源码二分：

class Solution {
    public boolean isPerfectSquare(int num) {
        int l = 1, r = num;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (num / mid < mid) r = mid - 1;
            else if (num / mid > mid) l = mid + 1;
            else return num % mid == 0;
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

y 总二分：

class Solution1 {
    public boolean isPerfectSquare(int num) {
        int l = 1, r = num;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (num / mid <= mid) r = mid;
            else l = mid + 1;
        }
        return (num / l == l) && (num % l == 0);
    }
}
1
2
3
4
5
6
7
8
9
10
11

双指针

双指针章节包含这里的所有题目，参考：【代码随想录】双指针法刷题

移除元素

题目：27. 移除元素

删除排序数组中的重复项

题目：26. 删除有序数组中的重复项 - 力扣（LeetCode）

凡是删除重复项都可用快慢指针。

移动零

题目：283. 移动零 - 力扣（LeetCode）

比较含退格的字符串

题目：844. 比较含退格的字符串 - 力扣（LeetCode）

有序数组的平方

题目：有序数组的平方

滑动窗口

长度最小的子数组

题目：209. 长度最小的子数组

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

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

滑动窗口（双指针）：

public int minSubArrayLen(int target, int[] nums) {
	int res = Integer.MAX_VALUE, sum = 0;
	for (int l = 0, r = 0; r < nums.length; r++) {
		sum += nums[r];
		while (sum >= target) { // 收缩左窗口
			res = Math.min(res, r - l + 1);
			sum -= nums[l++];
		}
	}
	return res % Integer.MAX_VALUE;
}
1
2
3
4
5
6
7
8
9
10
11

水果成篮

题目：904. 水果成篮 - 力扣（LeetCode）

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

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

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

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

HashMap + 滑动窗口：

public int totalFruit(int[] fruits) {
	int res = 0;
	Map<Integer, Integer> map = new HashMap<>(2);
	for (int l = 0, r = 0; r < fruits.length; r++) {
		map.put(fruits[r], map.getOrDefault(fruits[r], 0) + 1);
		// 滑动窗口内水果种类 > 2 时
		while (map.size() > 2) {
			map.put(fruits[l], map.get(fruits[l]) - 1);
			if (map.get(fruits[l]) == 0) map.remove(fruits[l]);
			l++;
		}
		res = Math.max(res, r - l + 1);
	}
	return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

使用数组优化 HashMap：

public int totalFruit(int[] fruits) {
	int[] map = new int[fruits.length];
	int res = 0, size = 0; // 当前水果种类
	for (int l = 0, r = 0; r < fruits.length; r++) {
		if (map[fruits[r]] == 0) size++;
		map[fruits[r]]++;
		// 滑动窗口内水果种类 > 2 时
		while (size > 2) {
			map[fruits[l]]--;
			if (map[fruits[l]] == 0) size--;
			l++;
		}
		res = Math.max(res, r - l + 1);
	}
	return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

最小覆盖子串

题目：76. 最小覆盖子串 - 力扣（LeetCode）

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

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

滑动窗口 + 双指针：

public String minWindow(String s, String t) {
	int[] map = new int[128]; // 记录字符出现次数
	for (char c : t.toCharArray()) map[c]--; // map[c]==-1 表示需要 1 个字符 c
	int count = 0; // 总共需要的字符数, count==t.length() 则满足最小覆盖子串
	// 记录最小覆盖串开始的 index 和 size
	int start = 0, size = Integer.MAX_VALUE;
	for (int l = 0, r = 0; r < s.length(); r++) {
		if (map[s.charAt(r)] < 0) count++; // 需要当前访问的字符
		map[s.charAt(r)]++; // 访问当前字符
		// 收缩窗口: map[c] > 0 表示不需要字符 c, 左指针可以往右移动
		while (l < r && map[s.charAt(l)] > 0) map[s.charAt(l++)]--;
		// 满足条件 并且 当前覆盖串长度更小, 则记录
		if (count == t.length() && r - l + 1 < size) {
			size = r - l + 1;
			start = l;
		}
	}
	return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

模拟

螺旋矩阵 II*

题目：59. 螺旋矩阵 II

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

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

模拟：右下左上，四个方向按顺序走

• 走前：判断是否越界、是否已访问。
• 走完：标记当前位置已访问。
• 第一个位置需要手动走。

public int[][] generateMatrix(int n) {
    int[][] res = new int[n][n];
    int i = 0, j = 0, cur = 2;
    res[0][0] = 1; // 手动走第一个位置
    while (cur <= n * n) {
        while (j < n - 1 && res[i][j + 1] == 0) res[i][++j] = cur++; // 右
        while (i < n - 1 && res[i + 1][j] == 0) res[++i][j] = cur++; // 下
        while (j > 0 && res[i][j - 1] == 0) res[i][--j] = cur++; // 左
        while (i > 0 && res[i - 1][j] == 0) res[--i][j] = cur++; // 上
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12

螺旋矩阵

题目：54. 螺旋矩阵 - 力扣（LeetCode）

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

输入：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]
1
2
3
4
5
6

public List<Integer> spiralOrder(int[][] matrix) {
	final int INF = 0x3f3f3f3f; // 无穷大标记为已访问
	List<Integer> res = new ArrayList<>();
	res.add(matrix[0][0]); // 第一个元素手动处理
	matrix[0][0] = INF; 
	int m = matrix.length, n = matrix[0].length;
	int k = m * n;
	int x = 0, y = 0;
	while (k-- > 1) {
		while (y < n - 1 && matrix[x][y + 1] != INF) { // 右
			res.add(matrix[x][++y]);
			matrix[x][y] = INF;
		}
		while (x < m - 1 && matrix[x + 1][y] != INF) { // 下
			res.add(matrix[++x][y]);
			matrix[x][y] = INF;
		}
		while (y > 0 && matrix[x][y - 1] != INF) { // 左
			res.add(matrix[x][--y]);
			matrix[x][y] = INF;
		}
		while (x > 0 && matrix[x - 1][y] != INF) { // 上
			res.add(matrix[--x][y]);
			matrix[x][y] = INF;
		}
	}
	return res;
}
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
26
27
28

顺时针打印矩阵

题目：剑指 Offer 29. 顺时针打印矩阵 - 力扣（LeetCode）

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

输入：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]
1
2
3
4
5
6

此题同螺旋矩阵。

public int[] spiralOrder(int[][] matrix) {
	if (matrix.length == 0) return new int[] {};
	final int INF = 0x3f3f3f3f; // 无穷大标记为已访问
	int m = matrix.length, n = matrix[0].length;
	int[] res = new int[m * n];
	res[0] = matrix[0][0]; // 第一个元素手动处理
	matrix[0][0] = INF;
	int x = 0, y = 0, k = 1; // k 从第二个元素开始放
	while (k < m * n) {
		while (y < n - 1 && matrix[x][y + 1] != INF) {
			res[k++] = matrix[x][++y];
			matrix[x][y] = INF;
		}
		while (x < m - 1 && matrix[x + 1][y] != INF) {
			res[k++] = matrix[++x][y];
			matrix[x][y] = INF;
		}
		while (y > 0 && matrix[x][y - 1] != INF) {
			res[k++] = matrix[x][--y];
			matrix[x][y] = INF;
		}
		while (x > 0 && matrix[x - 1][y] != INF) {
			res[k++] = matrix[--x][y];
			matrix[x][y] = INF;
		}
	}
	return res;
}
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
26
27
28