hot100技巧题解

136. 只出现一次的数字

问题描述

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

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

输出：1

示例 2 ：

输入：nums = [4,1,2,1,2]

输出：4

示例 3 ：

输入：nums = [1]

输出：1

提示：

• $1 <= nums.length <= 3 * 10^4$
• $-3 * 10^4 <= nums[i] <= 3 * 10^4$
• 除了某个元素只出现一次以外，其余每个元素均出现两次。

题解

问题分析

本题要求找出一个数组中只出现一次的元素，且其他元素均出现两次。为了满足线性时间复杂度 (O(n)) 且使用常量空间的要求，可以利用 异或运算 的性质。

异或运算的性质

1. a ^ a = 0：任何数与其本身异或的结果是 0。
2. a ^ 0 = a：任何数与 0 异或的结果是它本身。
3. 异或是交换律和结合律：即 a ^ b ^ c = a ^ c ^ b，可以任意调整操作顺序。

基于上述性质，如果我们对数组中的所有元素进行异或运算，所有出现两次的元素最终会相互抵消（因为 a ^ a = 0），最终剩下的就是那个只出现一次的元素。

解法思路

1. 初始化一个变量 res 为 0。
2. 遍历数组中的每个元素，将其与 res 进行异或运算。
3. 最终，res 的值就是那个只出现一次的元素。

代码实现

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int num : nums) {
            res ^= num;  // 将每个元素与res异或
        }
        return res;
    }
};

int main() {
    Solution solution;
    
    // 示例 1
    vector<int> nums1 = {2, 2, 1};
    cout << solution.singleNumber(nums1) << endl;  // 输出: 1
    
    // 示例 2
    vector<int> nums2 = {4, 1, 2, 1, 2};
    cout << solution.singleNumber(nums2) << endl;  // 输出: 4
    
    // 示例 3
    vector<int> nums3 = {1};
    cout << solution.singleNumber(nums3) << endl;  // 输出: 1
    
    return 0;
}

代码解释

1. 变量初始化：res = 0。
   • 这里的 res 用来存储最终的结果，初始为 0，因为与 0 进行异或操作不会改变任何数字。
2. 遍历数组：对数组中的每个元素 num 执行异或操作 res ^= num。
   • 对于数组中出现两次的数字，它们会互相抵消，最终剩下的 res 就是那个只出现一次的数字。
3. 返回结果：循环结束后，res 保存了只出现一次的数字，直接返回。

时间和空间复杂度

• 时间复杂度：O(n)，其中 n 是数组的长度。我们只遍历了一次数组，因此时间复杂度为线性。
• 空间复杂度：O(1)，我们只用了一个额外的变量 res 来存储中间结果，因此空间复杂度是常量。

示例解析

示例 1

输入：

nums = [2, 2, 1]

1. 初始 res = 0。
2. 第一次异或：res = 0 ^ 2 = 2。
3. 第二次异或：res = 2 ^ 2 = 0。
4. 第三次异或：res = 0 ^ 1 = 1。
5. 返回 res = 1，即为只出现一次的数字。

输出：

1

示例 2

输入：

nums = [4, 1, 2, 1, 2]

1. 初始 res = 0。
2. 第一次异或：res = 0 ^ 4 = 4。
3. 第二次异或：res = 4 ^ 1 = 5。
4. 第三次异或：res = 5 ^ 2 = 7。
5. 第四次异或：res = 7 ^ 1 = 6。
6. 第五次异或：res = 6 ^ 2 = 4。
7. 返回 res = 4，即为只出现一次的数字。

输出：

4

示例 3

输入：

nums = [1]

1. 初始 res = 0。
2. 第一次异或：res = 0 ^ 1 = 1。
3. 返回 res = 1，即为只出现一次的数字。

输出：

1

总结

通过异或运算，我们能够在 O(n) 时间复杂度内找到数组中只出现一次的数字，且只需要常量级的额外空间。这个解法非常高效，符合题目要求。

169. 多数元素

问题描述

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

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

示例 2：

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

提示：

• n == nums.length
• $1 <= n <= 5 * 10^4$
• $-10^9 <= nums[i] <= 10^9$

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

题解

问题分析

在这个问题中，我们需要找出数组中的多数元素，即出现次数超过 n / 2 的元素。给定的问题保证存在多数元素，因此我们不需要考虑没有多数元素的情况。

进阶要求

要求时间复杂度为 O(n)，空间复杂度为 O(1)，因此不能使用额外的哈希表或排序等方法，这意味着我们需要找到一个高效的算法。

解法：Boyer-Moore 投票算法

Boyer-Moore 投票算法是解决多数元素问题的经典算法，具有 O(n) 的时间复杂度和 O(1) 的空间复杂度。其核心思想是通过一个投票过程来找到可能的多数元素。

关键思路

1. 候选者和计数器：
   • 我们维护一个候选元素和一个计数器。
   • 初始化时，候选元素为数组的第一个元素，计数器为 1。
2. 遍历数组：
   • 如果当前元素与候选元素相同，计数器加 1。
   • 如果当前元素与候选元素不同，计数器减 1。
   • 当计数器为 0 时，重新选择一个新的候选元素，并将计数器重置为 1。
3. 最终结果：
   • 因为多数元素的出现次数超过数组长度的一半，经过遍历后，最后留下的候选元素一定是多数元素。

代码实现

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = nums[0];
        int count = 1;
        
        // 投票过程
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] == candidate) {
                count++;
            } else {
                count--;
            }
            
            if (count == 0) {
                candidate = nums[i];
                count = 1;
            }
        }
        
        return candidate;
    }
};

int main() {
    Solution solution;
    
    // 示例 1
    vector<int> nums1 = {3, 2, 3};
    cout << solution.majorityElement(nums1) << endl;  // 输出: 3
    
    // 示例 2
    vector<int> nums2 = {2, 2, 1, 1, 1, 2, 2};
    cout << solution.majorityElement(nums2) << endl;  // 输出: 2
    
    return 0;
}

代码解释

1. 初始化：
   • candidate 是我们当前的候选多数元素。
   • count 是一个计数器，用来追踪候选元素的出现次数。
2. 遍历数组：
   • 对于数组中的每个元素，我们根据与 candidate 的比较结果更新 count。
   • 如果 count 变为 0，说明当前的 candidate 已经没有足够的票数，重新选择一个新的候选元素，并将 count 重置为 1。
3. 返回结果：
   • 最终返回的 candidate 就是数组中的多数元素。

时间和空间复杂度

• 时间复杂度：O(n)，我们只遍历了一次数组。
• 空间复杂度：O(1)，我们只使用了常量空间来存储候选元素和计数器。

示例解析

示例 1

输入：

nums = [3, 2, 3]

1. 初始时，candidate = 3，count = 1。
2. 第一个元素 3 与 candidate 相同，count = 2。
3. 第二个元素 2 与 candidate 不同，count = 1。
4. 第三个元素 3 与 candidate 相同，count = 2。
5. 最终 candidate = 3，是多数元素。

输出：

3

示例 2

输入：

nums = [2, 2, 1, 1, 1, 2, 2]

1. 初始时，candidate = 2，count = 1。
2. 第一个元素 2 与 candidate 相同，count = 2。
3. 第二个元素 2 与 candidate 相同，count = 3。
4. 第三个元素 1 与 candidate 不同，count = 2。
5. 第四个元素 1 与 candidate 不同，count = 1。
6. 第五个元素 1 与 candidate 不同，count = 0，此时重新选择 candidate = 1，count = 1。
7. 第六个元素 2 与 candidate 不同，count = 0，此时重新选择 candidate = 2，count = 1。
8. 第七个元素 2 与 candidate 相同，count = 2。
9. 最终 candidate = 2，是多数元素。

输出：

2

总结

通过 Boyer-Moore 投票算法，我们能够以 O(n) 的时间复杂度和 O(1) 的空间复杂度解决多数元素问题。这个解法非常高效，符合题目要求。

75. 颜色分类

问题描述

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

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

示例 2：

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

提示：

• n == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2

进阶：

• 你能想出一个仅使用常数空间的一趟扫描算法吗？

题解

问题分析

我们需要对数组进行原地排序，使得所有 0 元素排在最前面，1 元素排在中间，2 元素排在最后面。由于数组元素只有 0、1 和 2，这是一个典型的“颜色分类”问题。

解法

可以使用 荷兰国旗问题 的解决方案，这是一种非常高效的排序方法，要求在 O(n) 时间内并且只使用常数空间完成排序。

荷兰国旗问题思路

1. 使用三个指针：
   • low：指向当前最小值的末尾（即 0 的右边界）。
   • mid：指向当前正在检查的元素。
   • high：指向当前最大值的前面（即 2 的左边界）。
2. 遍历数组：
   • 如果 nums[mid] == 0，则将其交换到 low 指针的位置，low 和 mid 都向右移动。
   • 如果 nums[mid] == 1，则直接跳过 mid，mid 向右移动。
   • 如果 nums[mid] == 2，则将其交换到 high 指针的位置，high 向左移动，mid 不变（因为交换过来的元素还需要判断）。
3. 终止条件：当 mid > high 时，排序完成。

代码实现

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int low = 0, mid = 0, high = nums.size() - 1;
        
        // 遍历数组
        while (mid <= high) {
            if (nums[mid] == 0) {
                // 如果是0，放到低位
                swap(nums[low], nums[mid]);
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                // 如果是1，跳过
                mid++;
            } else {
                // 如果是2，放到高位
                swap(nums[mid], nums[high]);
                high--;
            }
        }
    }
};

int main() {
    Solution solution;
    
    // 示例 1
    vector<int> nums1 = {2, 0, 2, 1, 1, 0};
    solution.sortColors(nums1);
    for (int num : nums1) {
        cout << num << " ";
    }
    cout << endl;  // 输出: 0 0 1 1 2 2
    
    // 示例 2
    vector<int> nums2 = {2, 0, 1};
    solution.sortColors(nums2);
    for (int num : nums2) {
        cout << num << " ";
    }
    cout << endl;  // 输出: 0 1 2
    
    return 0;
}

代码解释

1. 初始化指针：
   • low = 0：表示 0 的右边界。
   • mid = 0：当前正在检查的元素。
   • high = nums.size() - 1：表示 2 的左边界。
2. 遍历数组：
   • 如果当前元素是 0，就将它交换到 low 指针位置，并将 low 和 mid 向右移动。
   • 如果当前元素是 1，就直接跳过，继续检查下一个元素。
   • 如果当前元素是 2，就将它交换到 high 指针位置，并将 high 向左移动。注意，此时 mid 不动，因为交换过来的元素还需要判断。
3. 循环终止：
   • 当 mid > high 时，排序完成。

时间复杂度和空间复杂度

• 时间复杂度：O(n)，我们只遍历一次数组，每个元素最多交换一次。
• 空间复杂度：O(1)，只使用了常数空间。

示例解析

示例 1

输入：

nums = [2, 0, 2, 1, 1, 0]

1. 初始时：low = 0, mid = 0, high = 5。
2. nums[mid] == 2，交换 nums[mid] 和 nums[high]，然后 high--，此时 nums = [0, 0, 2, 1, 1, 2]，low = 0, mid = 0, high = 4。
3. nums[mid] == 0，交换 nums[mid] 和 nums[low]，然后 low++，mid++，此时 nums = [0, 0, 2, 1, 1, 2]，low = 1, mid = 1, high = 4。
4. nums[mid] == 0，交换 nums[mid] 和 nums[low]，然后 low++，mid++，此时 nums = [0, 0, 1, 1, 2, 2]，low = 2, mid = 2, high = 4。
5. nums[mid] == 1，mid++，此时 nums = [0, 0, 1, 1, 2, 2]，low = 2, mid = 3, high = 4。
6. nums[mid] == 1，mid++，此时 nums = [0, 0, 1, 1, 2, 2]，low = 2, mid = 4, high = 4。
7. mid > high，循环终止。

输出：

0 0 1 1 2 2

示例 2

输入：

nums = [2, 0, 1]

输出：

0 1 2

总结

通过 荷兰国旗问题 的解法，能够在 O(n) 时间内并且使用 O(1) 空间对数组进行排序。这种方法高效且简洁，适用于只有三种不同元素的排序问题。

31. 下一个排列

问题描述

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

• 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

• 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
• 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
• 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

必须 原地 修改，只允许使用额外常数空间。

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [1,1,5]
输出：[1,5,1]

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

题解

问题分析

这个问题要求我们找到给定整数数组的下一个排列，并且必须原地修改数组。下一个排列是指在字典序中比当前排列稍大的排列。如果当前排列是最大的字典序排列，则返回最小的排列。

思路

为了找到下一个排列，可以遵循以下步骤：

1. 从右向左查找：从右侧开始，找到第一个破坏递增顺序的位置 i，即 nums[i] < nums[i+1]。如果不存在这样的 i，则说明整个数组已经是降序排列，需要返回数组的最小排列（即升序排列）。
2. 从右向左查找比 nums[i] 大的数：在步骤 1 找到的 i 位置上，接下来需要找一个比 nums[i] 大的数来交换位置。具体做法是从数组的右端开始查找第一个比 nums[i] 大的数 nums[j]。
3. 交换位置：交换 nums[i] 和 nums[j]。
4. 反转数组：最后，将 i+1 到数组末尾的部分进行反转，使得这一部分变为升序，从而得到字典序最小的排列。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        
        // Step 1: Find the first descending element from the end
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        
        // If i >= 0, it means we found the first descending element
        if (i >= 0) {
            // Step 2: Find the smallest element greater than nums[i]
            int j = n - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            
            // Step 3: Swap nums[i] and nums[j]
            swap(nums[i], nums[j]);
        }
        
        // Step 4: Reverse the portion after index i
        reverse(nums.begin() + i + 1, nums.end());
    }
};

int main() {
    Solution solution;
    
    // Example 1
    vector<int> nums1 = {1, 2, 3};
    solution.nextPermutation(nums1);
    for (int num : nums1) {
        cout << num << " ";
    }
    cout << endl;  // Output: 1 3 2
    
    // Example 2
    vector<int> nums2 = {3, 2, 1};
    solution.nextPermutation(nums2);
    for (int num : nums2) {
        cout << num << " ";
    }
    cout << endl;  // Output: 1 2 3
    
    // Example 3
    vector<int> nums3 = {1, 1, 5};
    solution.nextPermutation(nums3);
    for (int num : nums3) {
        cout << num << " ";
    }
    cout << endl;  // Output: 1 5 1
    
    return 0;
}

代码解释

1. 找到第一个破坏递增顺序的位置 i：
   • 从右往左扫描，找到第一个 nums[i] < nums[i + 1] 的位置。这是因为如果整个数组从右向左是递减的，意味着没有更大的排列，返回最小排列（升序排列）。
2. 找到比 nums[i] 大的元素 nums[j]：
   • 通过从右端开始查找第一个大于 nums[i] 的数，这样可以保证交换后得到的数列仍然是字典序最小的。
3. 交换 nums[i] 和 nums[j]：
   • 交换后，nums[i] 变得比原来的 nums[j] 小，同时让其他部分变得尽可能小。
4. 反转 nums[i+1:]：
   • 为了确保数组的后半部分仍然是字典序最小的，我们需要反转它。

时间复杂度和空间复杂度

• 时间复杂度：O(n)，我们遍历了数组两次，一次是从右到左找到 i，另一次是从右到左找到 j，最终还需要反转后半部分。因此，时间复杂度是线性的。
• 空间复杂度：O(1)，我们只使用了常数空间来进行交换和反转操作，因此空间复杂度是常数的。

示例解析

示例 1

输入：

nums = [1, 2, 3]

1. 找到第一个破坏递增顺序的位置 i = 1（因为 2 < 3）。
2. 从右边找到比 2 大的数是 3，交换它们，得到 nums = [1, 3, 2]。
3. 反转 i+1 到数组末尾的部分，nums 保持不变，结果是 [1, 3, 2]。

输出：

1 3 2

示例 2

输入：

nums = [3, 2, 1]

1. 数组是完全递减的，没有找到合适的 i。
2. 反转整个数组，得到最小排列 [1, 2, 3]。

输出：

1 2 3

示例 3

输入：

nums = [1, 1, 5]

1. 找到第一个破坏递增顺序的位置 i = 1。
2. 从右边找到比 1 大的数是 5，交换它们，得到 nums = [1, 5, 1]。
3. 反转 i+1 到数组末尾的部分，得到 [1, 5, 1]。

输出：

1 5 1

总结

该算法使用了三步法（查找破坏递增序列的元素，找到比该元素大的数进行交换，反转后续部分），实现了对数组的原地修改，且时间复杂度为 O(n)，空间复杂度为 O(1)。这是解决该问题的最优解法。

287. 寻找重复数

问题描述

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

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

示例 2：

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

示例 3 :

输入：nums = [3,3,3,3,3]
输出：3

提示：

• 1 <= n <= 105
• nums.length == n + 1
• 1 <= nums[i] <= n
• nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次

进阶：

• 如何证明 nums 中至少存在一个重复的数字?
• 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

题解

问题分析

在这个问题中，我们有一个长度为 n + 1 的数组 nums，数组的元素在 [1, n] 范围内。根据题目要求，数组中至少有一个数字是重复的，而且我们不能修改数组，并且只能使用常量空间。

为了找到这个重复的数字，我们可以利用二分查找和Floyd 判圈算法（也称为快慢指针算法）来实现O(n) 时间复杂度和O(1) 空间复杂度的解法。

解法

1. 快慢指针法（Floyd 判圈算法）

这个算法是通过模拟链表的循环结构来找到重复元素的。具体步骤如下：

1. 将数组看作一个链表：每个数字的值代表着下一个索引。假设 nums[i] 表示从索引 i 到下一个索引的位置。因此，数组 nums 可以看作一个链表，链表的节点是数组元素的值，而数组元素的值则是指向下一个节点的指针。
2. 找环入口：利用快慢指针的方式找到一个环。慢指针每次走一步，快指针每次走两步。由于数组中存在重复元素，最终会导致某些值相同的元素会指向同一个位置，从而形成一个环。
3. 定位重复数字：一旦快慢指针相遇，说明存在环。此时，将一个指针移到起始位置，另一个指针从相遇位置出发，两个指针每次都走一步，最终会相遇在环的入口，这个入口即是重复数字。

算法步骤

1. 初始化快慢指针 slow 和 fast，分别指向数组的第一个元素。
2. 移动快慢指针，直到两者相遇，表示找到环。
3. 一旦相遇，重新设置一个指针从数组的起点出发，再次使用快慢指针方式，直到两者相遇，交点即为重复的数字。

代码实现

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        // Step 1: Initialize slow and fast pointers
        int slow = nums[0];
        int fast = nums[0];
        
        // Step 2: Find the intersection point of the two pointers (inside the cycle)
        do {
            slow = nums[slow];            // slow moves one step
            fast = nums[nums[fast]];      // fast moves two steps
        } while (slow != fast);
        
        // Step 3: Find the entry point of the cycle (the duplicate number)
        slow = nums[0];  // move slow pointer to the start
        while (slow != fast) {
            slow = nums[slow];  // move both pointers one step at a time
            fast = nums[fast];
        }
        
        return slow;  // The duplicate number
    }
};

int main() {
    Solution solution;
    
    // Example 1
    vector<int> nums1 = {1, 3, 4, 2, 2};
    cout << "Duplicate: " << solution.findDuplicate(nums1) << endl;  // Output: 2
    
    // Example 2
    vector<int> nums2 = {3, 1, 3, 4, 2};
    cout << "Duplicate: " << solution.findDuplicate(nums2) << endl;  // Output: 3
    
    // Example 3
    vector<int> nums3 = {3, 3, 3, 3, 3};
    cout << "Duplicate: " << solution.findDuplicate(nums3) << endl;  // Output: 3
    
    return 0;
}

代码解释

1. 初始化快慢指针：slow 和 fast 都指向数组的第一个元素 nums[0]。
2. 找环：快指针每次走两步，慢指针每次走一步。如果存在环，最终快慢指针会相遇。
3. 找环入口：当快慢指针相遇后，重新将慢指针指向数组的起始位置，再用两个指针每次走一步，直到它们再次相遇，位置即为重复的数字。

时间复杂度和空间复杂度

• 时间复杂度：O(n)。快慢指针的相遇过程最多走 O(n) 步，并且我们需要再走一次来找到环的入口，因此总时间复杂度为 O(n)。
• 空间复杂度：O(1)。我们只使用了常量的额外空间，不需要额外的存储结构。

示例解析

示例 1

输入：

nums = [1, 3, 4, 2, 2]

• 快慢指针开始移动，最终在某一位置相遇。
• 重置指针，最终找到重复数字是 2。

输出：

2

示例 2

输入：

nums = [3, 1, 3, 4, 2]

• 快慢指针开始移动，最终在某一位置相遇。
• 重置指针，最终找到重复数字是 3。

输出：

3

示例 3

输入：

nums = [3, 3, 3, 3, 3]

• 快慢指针开始移动，最终在某一位置相遇。
• 重置指针，最终找到重复数字是 3。

输出：

3

总结

该算法利用快慢指针法（Floyd 判圈算法），在不修改数组并且使用常量空间的情况下，成功找到了数组中的重复数字。它的时间复杂度为 O(n)，空间复杂度为 O(1)，是最优解法。