219. Contains Duplicate II

Problem

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

https://leetcode.cn/problems/contains-duplicate-ii/

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

Constraints:

1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
0 <= k <= 10⁵

Test Cases

1 2	class Solution: def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:

solution_test.py

import pytest

from solution import Solution


@pytest.mark.parametrize('nums, k, expected', [
    ([1,2,3,1], 3, True),
    ([1,0,1,1], 1, True),
    ([1,2,3,1,2,3], 2, False),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, nums, k, expected):
    assert sol.containsNearbyDuplicate(nums, k) == expected

Thoughts

跟 217. Contains Duplicate 差不多，增加了对元素下标间距的限制。可以把集合改成字典，记录见到的数字所在的下标，如果再次见到相同的数字，比较一下两次的下标即可。

Code

solution.py

class Solution:
    def containsNearbyDuplicate(self, nums: list[int], k: int) -> bool:
        known: dict[int, int] = {}
        for i, num in enumerate(nums):
            if num in known and i - known[num] <= k:
                return True
            known[num] = i

        return False

本文引用
- 217. Contains Duplicate

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。