LeetCode 219. Contains Duplicate II

LeetCode 219. Contains Duplicate II 题解
题目描述
  • 英文:

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

  • 中文:

给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 ij,使得 nums [i] = nums [j],并且 ij 的差的绝对值最大为 k

示例
  • 示例 1:
1
2
输入: nums = [1,2,3,1], k = 3
输出: true
  • 示例 2:
1
2
输入: nums = [1,0,1,1], k = 1
输出: true
  • 示例 3:
1
2
输入: nums = [1,2,3,1,2,3], k = 2
输出: false
题解
  • 题解 1

  使用字典来进行处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def containsNearbyDuplicate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
length = len(nums)
if length <= 1:
return False
dic = {}
for i in range(length):
if nums[i] in dic:
if i-dic[nums[i]] <= k:
return True
dic[nums[i]] = i
return False

  可以使用 217. Contains Duplicate 题中的方法稍作改进,使用 set() 方法得到不重复元素的集合,然后判断列表长度是否等于集合的长度,如果是则表示列表中没有重复的元素,直接返回 False。否则,进行上面的操作来做进一步的判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def containsNearbyDuplicate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
length = len(nums)
if length == len(set(nums)): # 改进的地方
return False
if length <= 1:
return False
dic = {}
for i in range(length):
if nums[i] in dic:
if i-dic[nums[i]] <= k:
return True
dic[nums[i]] = i
return False
  • 题解 2

  使用集合,集合中只存放 k 个元素,即满足题目要求的两个索引 ij 的差的绝对值最大为。遍历数组,每次判断元素是否在集合中,如果在,则表示有满足条件的重复元素,返回 True,并且每次都将元素加入到集合中,判断集合中元素个数是否大于 k,如果大于,则将第一个元素移除,保证集合中元素的索引与当前元素的索引相差最大为 k,即只考虑当前元素的前面 k 个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def containsNearbyDuplicate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
record = set()
for i in range(len(nums)):
if nums[i] in record: # 有满足条件的重复元素
return True
record.add(nums[i]) # 加入到集合
if len(record) == k + 1: # 保证集合中只有 k 个元素
record.remove(nums[i - k]) # 移除最前面的元素
return False
坚持原创技术分享,您的支持将鼓励我继续创作!