算法刷题记录——LeetCode篇(6) [第501~600题](持续更新)

更新时间：2025-03-19

• LeetCode刷题目录：算法刷题记录——专题目录汇总
• 技术博客总目录：计算机技术系列博客——目录页

优先整理热门100及面试150，不定期持续更新，欢迎关注！

---

543. 二叉树的直径

给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。

示例 1：

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

解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

示例 2：

输入：root = [1,2]
输出：1

提示：

• 树中节点数目在范围 [1, 10^4] 内
• -100 <= Node.val <= 100

方法：深度优先搜索（DFS）

利用递归计算每个节点的左右子树深度，在递归过程中更新最大直径。

1. 递归计算深度：对于每个节点，递归计算其左右子树的深度。
2. 动态更新直径：在递归过程中，当前节点的直径等于左子树深度与右子树深度之和。通过全局变量 maxDiameter 记录遍历过程中遇到的最大直径。

代码实现(Java)：

class Solution {private int maxDiameter = 0;public int diameterOfBinaryTree(TreeNode root) {maxDepth(root);return maxDiameter;}private int maxDepth(TreeNode node) {if (node == null) {return 0;}int leftDepth = maxDepth(node.left);int rightDepth = maxDepth(node.right);// 更新当前最大直径（路径边数为左右深度之和）maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);// 返回当前节点的深度（左右子树最大深度 + 1）return Math.max(leftDepth, rightDepth) + 1;}
}

方法复杂度分析

1. 时间复杂度：O(n)，每个节点被访问一次。
2. 空间复杂度：O(h)，递归栈深度与树的高度相关，最坏情况下（树退化为链表）为 O(n)。

---

560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。

示例 1：

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

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

提示：

• 1 <= nums.length <= 2 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7

方法一：前缀和 + 哈希表

利用前缀和和哈希表来优化时间复杂度。核心思想是维护一个哈希表，记录每个前缀和出现的次数。遍历数组时，计算当前前缀和，并检查哈希表中是否存在前缀和为 currentSum - k 的键。若存在，则说明存在若干子数组的和为 k。通过这种方式，时间复杂度可降至 O(n)。

代码实现(Java)：

public class Solution {public int subarraySum(int[] nums, int k) {int count = 0;int currentSum = 0;Map<Integer, Integer> prefixSumMap = new HashMap<>();prefixSumMap.put(0, 1); // 初始前缀和为0出现1次for (int num : nums) {currentSum += num;// 检查是否存在前缀和为 currentSum - kif (prefixSumMap.containsKey(currentSum - k)) {count += prefixSumMap.get(currentSum - k);}// 更新当前前缀和的出现次数prefixSumMap.put(currentSum, prefixSumMap.getOrDefault(currentSum, 0) + 1);}return count;}
}

方法二：暴力枚举

遍历所有可能的子数组起点和终点，计算子数组的和是否为 k。时间复杂度为 O(n²)，适用于数据量较小的情况。

代码实现(Java)：

public class Solution {public int subarraySum(int[] nums, int k) {int count = 0;for (int i = 0; i < nums.length; i++) {int sum = 0;for (int j = i; j < nums.length; j++) {sum += nums[j];if (sum == k) {count++;}}}return count;}
}

方法三：前缀和数组（暴力枚举优化版）

预先计算前缀和数组，然后遍历所有可能的子数组，通过前缀和之差快速计算子数组和。时间复杂度仍为 O(n²)，但减少了重复计算。

代码实现(Java)：

public class Solution {public int subarraySum(int[] nums, int k) {int n = nums.length;int[] prefixSum = new int[n + 1];prefixSum[0] = 0;for (int i = 0; i < n; i++) {prefixSum[i + 1] = prefixSum[i] + nums[i];}int count = 0;for (int i = 0; i < n; i++) {for (int j = i + 1; j <= n; j++) {if (prefixSum[j] - prefixSum[i] == k) {count++;}}}return count;}
}

复杂度分析

1. 前缀和 + 哈希表：通过哈希表记录前缀和的出现次数，将时间复杂度优化至 O(n)，是本题的最优解。
2. 暴力枚举：适用于小规模数据，但时间复杂度为 O(n²)，不适用于大规模输入。
3. 前缀和数组：通过预处理前缀和减少计算量，但时间复杂度仍为 O(n²)。

---

(持续更新，未完待续)