首页 > 营销学院 > AI智能

LeetCode 565: 数组嵌套问题深度解析与DFS解法

LeetCode 第 565 题，又称数组嵌套，是一道考察对数组元素之间关系的理解和算法应用能力的中等难度题目。本文将带你深入剖析这道题的题意，探讨使用深度优先搜索 (DFS) 算法解决该问题的原理，并提供 Java 和 Python 的详细代码示例。此外，我们还将分析该算法的时间复杂度和空间复杂度，并探讨如何优化代码，使其更加高效。通过本文的学习，你将不仅掌握 LeetCode 565 题的解法，更能够提升对数组和 DFS 算法的理解和应用能力。

关键点

理解数组嵌套的含义，即将数组元素作为索引，形成链式关系。

掌握深度优先搜索 (DFS) 算法，并能将其应用于解决图或树的遍历问题。

能够分析算法的时间复杂度和空间复杂度，并根据实际情况进行优化。

熟悉 Java 和 Python 等编程语言，并能够编写清晰、高效的代码。

数组嵌套问题详解

什么是数组嵌套？

数组嵌套问题，给定一个包含 n 个整数的数组 nums，其中 nums[i] 的取值范围在 [0, n-1] 之间，且不存在重复的数字。可以将数组元素 nums[i] 作为索引，构成一个链式关系：i -> nums[i] -> nums[nums[i]] -> ... 。这个链式关系最终会形成一个环。我们的目标是找到最长的环的长度。

☞☞☞AI 智能聊天, 问答助手, AI 智能搜索, 免费无限量使用 DeepSeek R1 模型☜☜☜

举例说明：假设 nums = [5, 4, 0, 3, 1, 6, 2]，从索引 0 开始，我们可以得到如下的链式关系： 0 -> nums[0] = 5 5 -> nums[5] = 6 6 -> nums[6] = 2 2 -> nums[2] = 0

最终形成一个环：0 -> 5 -> 6 -> 2 -> 0，该环的长度为 4。

我们需要遍历整个数组，找到所有可能的环，并返回最长环的长度。

问题分析与解题思路

解决数组嵌套问题的关键在于理解数组元素之间的索引关系，并将问题转化为寻找最长环的问题。我们可以采用以下几种解题思路：

暴力搜索：遍历数组的每个元素，以该元素为起点，沿着链式关系进行搜索，直到遇到重复的元素或超出数组范围。记录每个环的长度，并返回最长环的长度。该方法的时间复杂度较高，为 O(n^2)。
深度优先搜索 (DFS)：从数组的每个元素开始，进行深度优先搜索，记录搜索路径上的元素。如果搜索过程中遇到重复的元素，则表示找到了一个环，计算环的长度。为了避免重复搜索，可以使用一个 visited 数组来标记已经访问过的元素。
并查集：将数组中的每个元素看作一个节点，如果 i -> nums[i]，则将节点 i 和节点 nums[i] 合并到同一个集合中。最终，每个集合代表一个环，计算最大集合的元素个数即可。

深度优先搜索 (DFS) 算法详解

DFS 算法原理

深度优先搜索 (DFS) 是一种用于遍历或搜索树或图的算法。该算法沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点 v 的所有边都己被探寻过，搜索将回溯到发现节点 v 的起始节点的那些未被访问的节点。该算法在图形搜索和人工智能等领域都有广泛的应用。

DFS 算法步骤：

从起始节点开始，访问该节点。
标记该节点为已访问。
选择该节点的一个未被访问的邻接节点，并从该邻接节点开始递归执行 DFS 算法。
如果当前节点的所有邻接节点都己被访问，则回溯到该节点的父节点，继续搜索其他未被访问的邻接节点。
重复以上步骤，直到所有节点都被访问。

使用 DFS 解决数组嵌套问题

在数组嵌套问题中，我们可以将数组看作一个图，数组的索引作为图的节点，数组元素之间的索引关系作为图的边。然后，我们可以使用 DFS 算法来遍历图，寻找最长的环。

使用 DFS 算法解决数组嵌套问题的步骤：

创建一个 visited 数组，用于标记已经访问过的节点。
遍历数组的每个元素，如果该元素未被访问，则从该元素开始进行 DFS 搜索。
在 DFS 搜索过程中，记录搜索路径上的元素。如果搜索过程中遇到重复的元素，则表示找到了一个环，计算环的长度。
更新最长环的长度。
返回最长环的长度。

DFS 算法能够系统性地探索数组中隐含的图结构，沿着每一条链尽可能深入地探索，然后回溯，有效地检测到所有可能的环。

Java 代码示例

class Solution {
    public int arrayNesting(int[] nums) {
        int n = nums.length;
        boolean[] visited = new boolean[n];
        int maxLength = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                int start = i;
                int count = 0;
                do {
                    visited[start] = true;
                    start = nums[start];
                    count++;
                } while (start != i);
                maxLength = Math.max(maxLength, count);
            }
        }
        return maxLength;
    }
}

代码解释：

arrayNesting(int[] nums): 这是解决数组嵌套问题的函数，它接受一个整数数组 nums 作为输入，并返回嵌套数组的最大长度。
int n = nums.length;: 这行代码获取输入数组 nums 的长度，并将该长度存储在变量 n 中。这用于设置循环的边界和访问数组元素。
boolean[] visited = new boolean[n];: 在此创建了一个名为 visited 的布尔数组。此数组的大小与输入数组 nums 相同，用于跟踪在遍历期间已访问的数组索引。最初，所有元素都设置为 false，表明没有任何索引被访问过。
int maxLength = 0;: 初始化变量 maxLength 为 0。此变量用于跟踪在数组中找到的最大嵌套数组的长度。当算法遍历 nums 数组时，此变量会更新。
for (int i = 0; i : 此 for 循环从索引 0 迭代到索引 n - 1，有效地遍历输入数组 nums 中的每个索引。变量 i 表示当前索引。
if (!visited[i]): 此条件检查当前索引 i 是否已在先前迭代中访问过。如果 visited[i] 为 false，则表示该索引尚未被访问，并且该算法将继续探索从该索引开始的嵌套数组。
int start = i;声明一个名为start的整数变量并将i的值赋给它。
int count = 0;: 初始化 count 变量为 0。此变量用于跟踪当前嵌套数组的长度。
do { ... } while (start != i);:这是一个 do-while 循环，它遵循嵌套数组，直到返回到起始索引 i，表明已经完成了循环。
visited[start] = true;: 在 do-while 循环内，此行代码将 visited[start] 设置为 true，表明已访问当前索引 start。这可以防止算法无限循环并确保每个索引只访问一次。
start = nums[start];: 这行代码将 start 变量更新为 nums[start] 处的值。这会沿着嵌套数组移动到下一个索引。
count++;: 在每次迭代中，此行代码将 count 变量增加 1，从而跟踪当前嵌套数组的长度。
maxLength = Math.max(maxLength, count);: 在 do-while 循环结束后，此行代码使用 Math.max() 函数将 maxLength 更新为当前 maxLength 值和变量 count 之间的较大值。这样可以确保 maxLength 始终包含算法找到的最大嵌套数组的长度。
return maxLength;: 在 for 循环结束后，此行代码返回 maxLength，即在数组中找到的最大嵌套数组的长度。总而言之，该算法使用嵌套数组来找到最大嵌套数组的长度。为了避免多次访问相同的数组，使用了辅助的visited[]数组。

Python 代码示例

class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        n = len(nums)
        visited = [False] * n
        max_length = 0

        for i in range(n):
            if not visited[i]:
                start = i
                count = 0
                while not visited[start]:
                    visited[start] = True
                    start = nums[start]
                    count += 1
                max_length = max(max_length, count)

        return max_length

代码解释：

def arrayNesting(self, nums: List[int]) -> int:: 这是解决数组嵌套问题的 Python 函数。它接受一个整数列表 nums 作为输入，并返回嵌套数组的最大长度。
n = len(nums): 这行代码获取输入列表 nums 的长度，并将该长度存储在变量 n 中。
visited = [False] * n: 创建了一个名为 visited 的布尔列表。此列表的大小与输入列表 nums 相同，用于跟踪在遍历期间已访问的列表索引。最初，所有元素都设置为 False，表示没有任何索引被访问过。
max_length = 0: 初始化变量 max_length 为 0。此变量用于跟踪在数组中找到的最大嵌套数组的长度。当算法遍历 nums 数组时，此变量会更新。
for i in range(n):: 此 for 循环从索引 0 迭代到索引 n - 1，有效地遍历输入列表 nums 中的每个索引。变量 i 表示当前索引。
if not visited[i]:: 此条件检查当前索引 i 是否已在先前迭代中访问过。如果 visited[i] 为 False，则表示该索引尚未被访问，并且该算法将继续探索从该索引开始的嵌套数组。
start = i: 声明一个名为 start 的整数变量并将 i 的值赋给它。
count = 0: 初始化 count 变量为 0。此变量用于跟踪当前嵌套数组的长度。
while not visited[start]:: 这是一个 while 循环，它遵循嵌套数组，直到访问了已经访问过的值。
visited[start] = True: 在 while 循环内，此行代码将 visited[start] 设置为 true，表明已访问当前索引 start。这可以防止算法无限循环并确保每个索引只访问一次。
start = nums[start]:这行代码将 start 变量更新为 nums[start] 处的值。这会沿着嵌套数组移动到下一个索引。
count += 1: 在每次迭代中，此行代码将 count 变量增加 1，从而跟踪当前嵌套数组的长度。
max_length = max(max_length, count): 在 while 循环结束后，此行代码使用 max() 函数将 max_length 更新为当前 max_length 值和变量 count 之间的较大值。这样可以确保 max_length 始终包含算法找到的最大嵌套数组的长度。
return max_length: 在 for 循环结束后，此行代码返回 max_length，即在数组中找到的最大嵌套数组的长度。与 Java 示例类似，此 Python 代码遵循 DFS 方法来确定输入数组中最长的嵌套数组的长度。通过使用 visited[] 数组，此实现避免了再次检查相同的索引，从而优化了性能。