leetcode
leetcode 201 ~ 250
存在重复元素 III

存在重复元素 III

难度:

标签:

题目描述

给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff 。

找出满足下述条件的下标对 (i, j)：

  • i != j,
  • abs(i - j) <= indexDiff
  • abs(nums[i] - nums[j]) <= 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 <= 105
  • -109 <= nums[i] <= 109
  • 1 <= indexDiff <= nums.length
  • 0 <= valueDiff <= 109

代码结果

运行时间: 83 ms, 内存: 33.1 MB

// Java Stream Solution
// 题目思路：
// 通过使用Java Stream API来简化数组的遍历和条件判断。
 
import java.util.stream.IntStream;
 
public class StreamSolution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        return IntStream.range(0, nums.length)
            .anyMatch(i -> IntStream.range(i + 1, Math.min(nums.length, i + indexDiff + 1))
                .anyMatch(j -> Math.abs((long)nums[i] - (long)nums[j]) <= valueDiff));
    }
}

解释

方法:

该题解使用了桶排序的思想。将数组按照 valueDiff 进行分桶，每个桶的大小为 valueDiff+1。对于每个元素，检查其所在的桶以及相邻的两个桶内是否存在满足条件的元素。如果找到了这样的元素对，就返回 True。为了满足 indexDiff 的限制，使用一个哈希表 bucket 来维护一个大小为 indexDiff 的滑动窗口，并在窗口滑动时及时删除旧桶。

时间复杂度:

O(n)

空间复杂度:

O(min(n, indexDiff))

代码细节讲解

🦆
在桶排序的思想中，为何选择桶的大小为valueDiff+1？这样的设置有何优势或特别之处？
▷
在桶排序的思想中，选择桶的大小为valueDiff+1是为了确保同一个桶中的任何两个元素之间的差值最大为valueDiff。这是因为如果两个元素的差值小于或等于valueDiff，它们除以valueDiff+1的结果将落在同一个桶中。此外，这种设置还避免了跨多个桶进行复杂的比较，如果桶的大小小于valueDiff+1，则可能需要检查更多相邻桶，增加复杂度。这样的设置简化了问题，使得只需要检查元素所在桶及其最多两个相邻桶。
🦆
题解中提到检查相邻桶时，如何确保比较的是满足indexDiff条件的元素？是否有可能比较到超出indexDiff范围的元素？
▷
题解中通过维护一个大小为indexDiff的滑动窗口来确保比较的元素满足indexDiff条件。具体来说，当遍历到新的元素时，如果其索引超出了当前窗口的范围（即大于等于indexDiff），则从哈希表中删除最早进入窗口的元素所在的桶。这样可以保证在哈希表中的任何元素都是距离当前元素索引差不超过indexDiff的元素。因此，即便检查相邻桶，也只会比较满足indexDiff条件的元素。
🦆
题解中删除桶元素的逻辑是基于窗口大小的，如果indexDiff非常小，是否可能在删除后又立即需要该桶的数据？这样的删除策略是否最优？
▷
虽然在indexDiff非常小的情况下，可能会出现删除后立即需要该桶数据的情况，但这种情况下仍需删除元素以保证每个元素与比较元素的索引差不超过indexDiff。这种删除策略是为了保证哈希表中仅包含滑动窗口内的元素，避免不符合条件的比较。虽然不是所有情况下都是最优的（如频繁的插入和删除操作可能导致效率低下），但它确保了算法的正确性和简化了实现。对于更优化的策略，可能需要根据具体的使用场景和性能测试结果来调整。
🦆
在特殊情况处理中，当valueDiff为0且数组中无重复元素时直接返回False，这种处理背后的逻辑是什么？能否解释一下这种情况下为什么不可能存在符合条件的元素对？
▷
当valueDiff为0时，题目要求的是数组中是否存在两个不同位置的元素值完全相同。如果数组中无重复元素（即所有元素都是唯一的），显然不可能找到两个值完全相同的元素。因此，在valueDiff为0且数组中无重复元素的情况下，直接返回False是正确的，因为不存在任何符合条件的元素对。这种处理有效地减少了不必要的计算，优化了算法性能。

相关问题

存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109

存在重复元素 II

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

 

示例 1：

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

示例 2：

输入：nums = [1,0,1,1], k = 1
输出：true

示例 3：

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

 

 

提示：

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • 0 <= k <= 105
存在重复元素 II最大正方形