LeetCode-Go 题解 220. Contains Duplicate III桶排序与滑动窗口求解存在重复元素 III【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文以 LeetCode-Go 仓库中 220. Contains Duplicate III 题解文档为核心系统讲解如何在整数数组中高效判断是否存在「数值差 ≤ t 且索引差 ≤ k」的数对。文章从 O(n²) 的暴力双指针思路出发逐步推导到排序 滑动窗口的 O(n log n) 方案最终深入剖析仓库源码采用的桶排序 O(n) 最优解法并结合测试用例给出可验证的边界条件与实现细节。读完本文你将掌握该类索引距离 数值距离双重约束问题的通用分析路径以及桶排序分桶映射在滑动窗口问题中的典型应用技巧。题目描述Given an array of integers, find out whether there are two distinct indices i and j in the array such that theabsolutedifference betweennums[i]andnums[j]is at most t and theabsolutedifference between i and j is at most k.给定一个整数数组nums判断数组中是否存在两个不同的下标i和j使得| nums[i] - nums[j] | ≤ t且| i - j | ≤ k。示例 1Input: nums [1,2,3,1], k 3, t 0 Output: true示例 2Input: nums [1,0,1,1], k 1, t 2 Output: true示例 3Input: nums [1,5,9,1,5,9], k 2, t 3 Output: false三个示例分别覆盖了同值数对距离够近示例 1、不同值但差值在 t 范围内示例 2、看似满足条件实则索引距离超限示例 3三类典型情况是后续验证算法正确性的关键样本。题目大意给出一个数组num再给出参数k和t。问在num中能否找到一组下标i和j使得num[i]和num[j]的绝对差值最大为t并且i和j之间的绝对差值最大为k。需要注意的是两个约束是且的关系既要数值接近≤ t又要下标接近≤ k。任何一个条件不满足数对都不合法。思路演进一暴力双指针枚举O(n²)最直观的想法是用i和j两个指针双重循环针对每个i从i 1往后扫描数组逐一判断是否满足| nums[i] - nums[j] | ≤ t同时用剪枝条件| i - j | ≤ k控制内层循环的扫描范围。仓库在 220. Contains Duplicate III.go 中保留了这一朴素实现containsNearbyAlmostDuplicate1// 解法二 滑动窗口 剪枝 func containsNearbyAlmostDuplicate1(nums []int, k int, t int) bool { if len(nums) 1 { return false } if k 0 { return false } n : len(nums) for i : 0; i n; i { count : 0 for j : i 1; j n count k; j { if abs(nums[i]-nums[j]) t { return true } count } } return false }该实现有以下要点内层循环通过count k限制扫描长度即最多向后看k个元素等价于剪枝条件| i - j | ≤ k借助辅助函数abs源码第 57-61 行计算绝对值提前处理两个退化场景len(nums) 1元素不足两个不可能存在不同下标和k 0索引距离约束失效。复杂度分析外层循环 O(n)内层最多扫描k个元素时间复杂度为 O(n·k)当k与n同量级时退化为 O(n²)。这个做法慢的原因在于滑动窗口的左边界和右边界在滑动过程中不是联动滑动的——每移动一次左边界i右边界都要重新从i 1扫起窗口信息完全没有被复用。这正是后续两种优化思路的切入点。思路演进二排序 联动滑动窗口O(n log n)既然无序数组中左右边界难以联动一个自然的想法是如果数组是有序的呢把数组按照元素值从小到大排序如果元素值相等则按照 index 从小到大排序。在这样有序的数组中寻找满足题意的i和j滑动窗口的左边界和右边界就能实现联动滑动窗口的右边界持续右滑直到与左边界的元素差值 ≤ t 的位置在此范围内判断| i - j | ≤ k一旦右边界与左边界元素值的差值 t说明左边界该向右移动了——因为数组已按元素大小排序右移左边界正是沿着增大元素的方向使得差值重新变小移动左边界时需要注意左边界不能超过右边界。这样滑动窗口一次滑过整个排序后的数组即可判断是否存在满足题意的i和j。这个做法的时间主要花在排序上时间复杂度为 O(n log n)空间复杂度 O(n)排序所需额外空间。思路演进三桶排序思想O(n)最优解本题的最优解利用桶排序的思想。仓库源码 220. Contains Duplicate III.go 中的containsNearbyAlmostDuplicate即为此解法// 解法一 桶排序 func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool { if k 0 || t 0 || len(nums) 2 { return false } buckets : map[int]int{} for i : 0; i len(nums); i { // Get the ID of the bucket from element value nums[i] and bucket width t 1 key : nums[i] / (t 1) // -7/9 0, but need -7/9 -1 if nums[i] 0 { key-- } if _, ok : buckets[key]; ok { return true } // check the lower bucket, and have to check the value too if v, ok : buckets[key-1]; ok nums[i]-v t { return true } // check the upper bucket, and have to check the value too if v, ok : buckets[key1]; ok v-nums[i] t { return true } // maintain k size of window if len(buckets) k { delete(buckets, nums[i-k]/(t1)) } buckets[key] nums[i] } return false }核心思想用桶压缩数值距离判断约束| i - j | ≤ k通过维护一个大小为 k 的滑动窗口来解决窗口内最多保留k个最近访问过的元素一旦窗口内已有k个元素再插入新元素前先删除最旧的那个从而保证当前元素与窗口内任意元素的索引差 ≤ k。约束| nums[i] - nums[j] | ≤ t是难点。利用桶排序思想将所有元素划分为若干个宽度为t 1的区间..., [0, t], [t1, 2t1], ...。每个元素根据其数值落入唯一的桶中桶编号由key nums[i] / (t 1)计算得出。由于每个桶的宽度恰好是t 1可以推出关键结论同一桶内的任意两个元素数值差必然 ≤ t数值差 ≤ t 的两个元素只可能落在同一个桶或相邻的两个桶中相距两个及以上桶的元素差值必然 t。因此对每个新元素只需进行3 次查找即可确定窗口内是否存在满足条件的数对。三桶查询的具体流程以当前元素nums[i]及其桶号key为准查询同桶若buckets[key]已存在说明窗口内已有元素落入同一桶二者数值差必然 ≤ t直接返回true查询前一个桶下桶界若buckets[key-1]存在且nums[i] - v t则命中——此时必须同时校验实际数值差因为相邻桶内元素并不必然满足条件查询后一个桶上桶界若buckets[key1]存在且v - nums[i] t同样命中同样需要校验实际数值差。若 3 次查询均未命中说明当前i找不到满足题意的j将当前元素写入桶中后继续循环。循环结束后仍未找到返回false。负数处理的实现细节源码中有一个容易忽略的细节第 12-15 行// -7/9 0, but need -7/9 -1 if nums[i] 0 { key-- }在 Go 中整数除法向零取整-7 / (t1)的结果为 0 而非 -1。若不加修正负数元素会被错误地分入0 号桶与正数元素混在一起破坏桶的数值区间定义导致漏判或误判。因此对负数元素需要将桶号再减 1使-7正确落入负桶区间。这一细节对负整数场景如测试用例中的[-3, -1]的正确性至关重要。窗口的维护与旧元素淘汰窗口大小为k的维护逻辑在 第 27-31 行// maintain k size of window if len(buckets) k { delete(buckets, nums[i-k]/(t1)) } buckets[key] nums[i]当窗口中的桶数量达到k时先删除下标为i-k的元素即窗口外最旧元素对应的桶再插入当前元素从而始终保证窗口内任意元素与当前元素的索引差 ≤ k。由于map中每个桶只保留该桶内最新访问的一个元素值窗口大小得以稳定控制。复杂度分析整个数组只遍历一遍每次操作查桶、插桶、删桶均为 O(1) 的哈希操作时间复杂度 O(n)空间复杂度 O(min(n, k))窗口中最多保留 k 个桶。这是相对排序方案O(n log n)的进一步优化。边界条件与防御性判断源码 第 5-7 行 对三类退化输入做了统一拦截if k 0 || t 0 || len(nums) 2 { return false }条件原因k 0索引距离约束失效任何不同下标都不满足\| i - j \| ≤ 0t 0数值差不可能为负\| nums[i] - nums[j] \| ≤ t 0无解注意t 0是合法输入对应找相等元素len(nums) 2元素不足两个不存在两个不同下标这三个条件同时也能防止后续除法运算中出现t 1 0的除零错误当t -1时t 1 0是一举两得的防御性设计。测试用例验证仓库在 220. Contains Duplicate III_test.go 中为两种解法编写了完整的表驱动测试。测试结构采用question220参数para220 答案ans220的封装模式对每种输入同时调用containsNearbyAlmostDuplicate与containsNearbyAlmostDuplicate1并逐一比对结果。测试用例覆盖了以下关键场景源码 第 29-90 行输入 (nums, k, t)期望输出覆盖点[7,1,3], 2, 3true一般命中场景[-1,-1], 1, -1false负数 负 tt 0 直接返回 false[1,2,3,1], 3, 0true题目示例 1t 0 找相等元素[1,0,1,1], 1, 2true题目示例 2相邻桶命中[1,5,9,1,5,9], 2, 3false题目示例 3索引距离超限[1,2,1,1], 1, 0true连续相等元素[2,4], 2, 2true最小规模数组命中[4,2], 2, 2true逆序输入[-3,-1], 2, 1false负数相邻桶但数值差 t[-3,-10], 2, 3false负数桶号修正后差值校验[5], 1, 1false单元素数组[1,2,3], 0, 1falsek 0 边界其中[-3, -1], k2, t1与[-3, -10], k2, t3两组负用例直接验证了负数桶号修正逻辑的正确性——若不进行key--修正负数元素会错误落入 0 号桶极可能导致误判为true。三种解法复杂度对比与总结解法核心思路时间复杂度空间复杂度代码位置暴力双指针 剪枝双重循环count k剪枝O(n·k)最坏 O(n²)O(1)220. Contains Duplicate III.go排序 联动滑动窗口元素有序化左右边界联动O(n log n)O(n)原题解思路文档论述桶排序最优宽度t1分桶 三桶查询 k 窗口O(n)O(min(n, k))220. Contains Duplicate III.go本题的价值在于它同时呈现了三种典型算法思维暴力枚举是一切问题的兜底方案其重复扫描窗口的缺陷指明了优化方向排序 滑动窗口展示了如何通过数据有序化换取指针联动是一种普适的降复杂度思路桶排序解法则将连续数值域离散化为t 1宽度的桶把数值差 ≤ t的判断压缩为常数次哈希查询是以空间换时间、以离散化换常数时间的经典范例与 219. Contains Duplicate II仅需判断相等元素相比本题多出的t维度正是由桶宽度吸收的。对于需要处理区间内数值相近类问题如范围查询、最近邻查找的开发者而言这套分桶 邻桶探测的框架具有很高的迁移价值。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考