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.

分析

判断是否包含重复数,且下标的差不超过给定值

  • 输入:一个无序数组和给定目标值
  • 条件:下标差值不大于给定目标值
  • 任务:判断是否包含重复数,且下标的差不超过给定值
  • 输出:True or False

代码

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

点评

用一个字典记录当前见到的数和其下标,遍历数组,判断当前值是否存在于字典中且下标之差不大于目标值,否则记录/更新当前值在字典中的下标,注意,因为是要求下标之差不大于目标值,所以可以直接覆盖之前的相同值

扩展

如果要求是下标之差不小于目标值的话,不能覆盖之前出现的值,如果之前存在,则直接跳过,不存在则记录