【LeetCode】存在重复元素 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

---

二、解法

滑动窗口 + 哈希表
既然限制了abs(i - j) <= k，那么，首先想到的应该是滑动窗口，来限制数的范围，然后使用哈希表来，检查是否有相同的元素出现

---

完整代码

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        left, right, n = 0, k, len(nums)
        dic = {}
        if n < 2:
            return False
        for i in range(min(n, k + 1)):
            dic[nums[i]] = dic.get(nums[i], 0) + 1
            if dic[nums[i]] > 1:
                return True
        while right < n - 1:
            dic[nums[left]] -= 1
            right += 1
            dic[nums[right]] = dic.get(nums[right], 0) + 1
            if dic[nums[right]] > 1:
                return True
            left += 1
        return False

---

原文地址：https://blog.csdn.net/qq_26521261/article/details/140362823

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！