【Swift算法实战】存在重复元素III

网罗开发 （小红书、快手、视频号同名）

  大家好，我是 展菲，目前在上市企业从事人工智能项目研发管理工作，平时热衷于分享各种编程领域的软硬技能知识以及前沿技术，包括iOS、前端、Harmony OS、Java、Python等方向。在移动端开发、鸿蒙开发、物联网、嵌入式、云原生、开源等领域有深厚造诣。

图书作者：《ESP32-C3 物联网工程开发实战》 图书作者：《SwiftUI 入门，进阶与实战》 超级个体：COC上海社区主理人 特约讲师：大学讲师，谷歌亚马逊分享嘉宾 科技博主：极星会首批签约作者

文章目录 摘要描述示例 1：示例 2：约束条件： 题解答案优化思路： 题解代码分析示例测试及结果时间复杂度空间复杂度总结

摘要

本问题要求在给定整数数组 nums 中找到一对 (i, j)，满足：

i != jabs(i - j) <= indexDiffabs(nums[i] - nums[j]) <= valueDiff

在大规模数据（最多 10^5 个元素）下，需要高效的算法来找到满足条件的索引对。本文将介绍如何使用 滑动窗口 + 平衡二叉搜索树（BST） 进行优化，并提供完整的 Swift 代码和分析。

描述

给定一个整数数组 nums 以及两个整数 indexDiff 和 valueDiff，需要判断是否存在满足以下条件的索引对 (i, j)：

i != jabs(i - j) <= indexDiff （索引之差在 indexDiff 范围内）abs(nums[i] - nums[j]) <= valueDiff （值之差在 valueDiff 范围内）

如果存在，返回 true，否则返回 false。

示例 1： 输入： nums = [1,2,3,1], indexDiff = 3, valueDiff = 0 输出： true 解释： 可以找出 (i, j) = (0, 3) 。 满足下述 3 个条件： i != j --> 0 != 3 abs(i - j) <= indexDiff --> abs(0 - 3) <= 3 abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0 示例 2： 输入： nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3 输出： false 解释： 尝试所有可能的下标对 (i, j) ，均无法满足这 3 个条件，因此返回 false 。 约束条件： 2 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^91 <= indexDiff <= nums.length0 <= valueDiff <= 10^9

题解答案

由于 nums 数组较大（长度 10^5），如果直接使用两层循环暴力遍历所有可能的 (i, j) 组合，时间复杂度将达到 O(n^2)，远远无法满足要求。因此，我们需要一个高效的数据结构来动态维护窗口内的数值范围。

优化思路： 滑动窗口 + 平衡二叉搜索树（BST，Swift 中用 SortedSet） 维护一个大小为 indexDiff 的滑动窗口。在滑动窗口内，利用 BST 进行二分查找，快速找到是否存在满足 abs(nums[i] - nums[j]) <= valueDiff 的元素。 题解代码分析 import Foundation func containsNearbyAlmostDuplicate(_ nums: [Int], _ indexDiff: Int, _ valueDiff: Int) -> Bool { guard indexDiff > 0, valueDiff >= 0 else { return false } var window = SortedSet<Int>() // Swift 没有内置的 SortedSet，这里可以用 Set + Array 手动实现 for i in 0..<nums.count { let num = nums[i] // 在窗口中找到是否有满足条件的数值 if let floor = window.floor(num) { // 找到 <= num 的最大值 if num - floor <= valueDiff { return true } } if let ceil = window.ceiling(num) { // 找到 >= num 的最小值 if ceil - num <= valueDiff { return true } } // 维护滑动窗口 window.insert(num) if i >= indexDiff { window.remove(nums[i - indexDiff]) } } return false } 示例测试及结果 let nums1 = [1, 2, 3, 1] let indexDiff1 = 3 let valueDiff1 = 0 print(containsNearbyAlmostDuplicate(nums1, indexDiff1, valueDiff1)) // 输出: true let nums2 = [1, 5, 9, 1, 5, 9] let indexDiff2 = 2 let valueDiff2 = 3 print(containsNearbyAlmostDuplicate(nums2, indexDiff2, valueDiff2)) // 输出: false 时间复杂度 插入 & 删除操作：O(log n)查询操作：O(log n)遍历所有元素：O(n)总时间复杂度：O(n log n)

相比于暴力 O(n^2) 的时间复杂度，这种方法大大提高了效率，使其能够处理更大的数据规模。

空间复杂度 维护一个最多 indexDiff 个元素的滑动窗口，空间复杂度为 O(indexDiff)，最坏情况下 O(n)。 总结 核心思路：利用 滑动窗口 + 平衡二叉搜索树（BST） 来高效地维护 indexDiff 范围内的数值。优点： 时间复杂度降至 O(n log n)，大幅优化暴力 O(n^2) 解法。空间复杂度 O(indexDiff)，比直接存储所有元素的 O(n) 更优。 适用场景： 适用于 数据规模较大 的情况，如 10^5 级别的数组。需要动态维护 窗口内最大最小值 时，可以借鉴此方法。