当前位置：首页 > article >正文

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

article 2025/3/19 23:00:51

(优先整理热门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）

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

递归计算深度：对于每个节点，递归计算其左右子树的深度。
动态更新直径：在递归过程中，当前节点的直径等于左子树深度与右子树深度之和。通过全局变量 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;
    }
}

方法复杂度分析

时间复杂度：O(n)，每个节点被访问一次。
空间复杂度：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 - k
            if (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;
    }
}