目录

1. 存在重复元素 Contains Duplicate I

2. 存在重复元素 Contains Duplicate II

3. 存在重复元素 Contains Duplicate III

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

---

1. 存在重复元素 Contains Duplicate I

给你一个整数数组 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 <= 10^5
• -10^9 <= nums[i] <= 10^9

代码： 多种方法实现

from typing import List
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] == nums[j]:
                    return True
        return False

    def containsDuplicate2(self, nums: List[int]) -> bool:
        num_set = set()
        for num in nums:
            if num in num_set:
                return True
            num_set.add(num)
        return False

    def containsDuplicate3(self, nums: List[int]) -> bool:
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                return True
        return False

    def containsDuplicate4(self, nums: List[int]) -> bool:
        return len(nums) != len(set(nums))


if __name__ == '__main__':
    s = Solution()
    nums = [1,2,3,1]
    print(s.containsDuplicate(nums))
    print(s.containsDuplicate2(nums))
    print(s.containsDuplicate3(nums))
    print(s.containsDuplicate4(nums))
    nums = [1,2,3,4]
    print(s.containsDuplicate(nums))
    print(s.containsDuplicate2(nums))
    print(s.containsDuplicate3(nums))
    print(s.containsDuplicate4(nums))
    nums = [1,1,1,3,3,4,3,2,4,2]
    print(s.containsDuplicate(nums))
    print(s.containsDuplicate2(nums))
    print(s.containsDuplicate3(nums))
    print(s.containsDuplicate4(nums))

输出：

True
True
True
True
False
False
False
False
True
True
True
True

---

2. 存在重复元素 Contains Duplicate 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 <= 10^5
• -10^9 <= nums[i] <= 10^9
• 0 <= k <= 10^5

代码： 多种方法实现

from typing import List
class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, min(i + k + 1, n)):
                if nums[i] == nums[j]:
                    return True
        return False

    def containsNearbyDuplicate2(self, nums: List[int], k: int) -> bool:
        num_index = {}
        for i in range(len(nums)):
            if nums[i] in num_index and i - num_index[nums[i]] <= k:
                return True
            num_index[nums[i]] = i
        return False

    def containsNearbyDuplicate3(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        if k >= n:
            k = n - 1
        num_set = set(nums[:k + 1])
        if len(num_set) != k + 1:
            return True
        for i in range(k + 1, n):
            num_set.remove(nums[i - k - 1])
            if nums[i] in num_set:
                return True
            num_set.add(nums[i])
        return False


if __name__ == '__main__':
    s = Solution()
    nums = [1,2,3,1]
    print(s.containsNearbyDuplicate(nums, 3))
    print(s.containsNearbyDuplicate2(nums, 3))
    print(s.containsNearbyDuplicate3(nums, 3))
    nums = [1,0,1,1]
    print(s.containsNearbyDuplicate(nums, 1))
    print(s.containsNearbyDuplicate2(nums, 1))
    print(s.containsNearbyDuplicate3(nums, 1))
    nums = [1,2,3,1,2,3]
    print(s.containsNearbyDuplicate(nums, 2))
    print(s.containsNearbyDuplicate2(nums, 2))
    print(s.containsNearbyDuplicate3(nums, 2))

输出：

True
True
True
True
True
True
False
False
False

---

3. 存在重复元素 Contains Duplicate III

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 0 <= nums.length <= 2 * 10^4
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^4
• 0 <= t <= 2^31 - 1

代码： 多种方法实现

from typing import List
import bisect
class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, min(i + k + 1, n)):
                if abs(nums[i] - nums[j]) <= t and abs(i - j) <= k:
                    return True
        return False

    def containsNearbyAlmostDuplicate2(self, nums: List[int], k: int, t: int) -> bool:
        n = len(nums)
        if t < 0 or k <= 0:
            return False
        bst = []
        for i in range(n):
            idx = bisect.bisect_left(bst, nums[i] - t)
            if idx < len(bst) and abs(bst[idx] - nums[i]) <= t:
                return True
            bisect.insort(bst, nums[i])
            if i >= k:
                bst.remove(nums[i - k])
        return False

    def containsNearbyAlmostDuplicate3(self, nums: List[int], k: int, t: int) -> bool:
        if t < 0 or k <= 0:
            return False
        n = len(nums)
        dic = dict()
        w = t + 1
        for i in range(n):
            m = nums[i] // w
            if m in dic:
                return True
            elif m - 1 in dic and abs(nums[i] - dic[m - 1]) < w:
                return True
            elif m + 1 in dic and abs(nums[i] - dic[m + 1]) < w:
                return True
            dic[m] = nums[i]
            if i >= k:
                del dic[nums[i - k] // w]
        return False


if __name__ == '__main__':
    s = Solution()
    nums = [1,2,3,1]
    print(s.containsNearbyAlmostDuplicate(nums, 3, 0))
    print(s.containsNearbyAlmostDuplicate2(nums, 3, 0))
    print(s.containsNearbyAlmostDuplicate3(nums, 3, 0))
    nums = [1,0,1,1]
    print(s.containsNearbyAlmostDuplicate(nums, 1, 2))
    print(s.containsNearbyAlmostDuplicate2(nums, 1, 2))
    print(s.containsNearbyAlmostDuplicate3(nums, 1, 2))
    nums = [1,5,9,1,5,9]
    print(s.containsNearbyAlmostDuplicate(nums, 2, 3))
    print(s.containsNearbyAlmostDuplicate2(nums, 2, 3))
    print(s.containsNearbyAlmostDuplicate3(nums, 2, 3))

输出：

True
True
True
True
True
True
False
False
False

---

🌟 每日一练刷题专栏 🌟

✨ 持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！ 

🌟 收藏，你的青睐是我努力的方向！ 

✎ 评论，你的意见是我进步的财富！  

☸ 主页：https://hannyang.blog.csdn.net/

	Golang每日一练 专栏
	Python每日一练 专栏
	C/C++每日一练 专栏
	Java每日一练 专栏