217. Contains Duplicate
https://leetcode.com/problems/contains-duplicate/#/description
Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
超简单思路
- 判断set之后的长度与原数组长度关系。。。
class Solution(object):
def containsDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if len(nums) <= 1:
return False
return len(set(nums)) != len(nums)
219. Contains Duplicate II
https://leetcode.com/problems/contains-duplicate-ii/#/description
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.
分析
- 建立字典dict={value：index}
- 遍历到i的value in dict，则判断index与i的关系
- 需要注意[1， 0， 1， 1]时，需要对1的位置进行更新，从0->2，
(因为这里位于0,2的距离较远，但是1,2的距离较近)
所以判断条件中需要加上 i - d[nums[1]] <= k，否则才对d进行更新 - key in d.keys() 等价于 key in d
- 注意，若不对len(set(nums)) == len(nums)进行判断，则会有个超长数组让你超时。。。
class Solution(object):
def containsNearbyDuplicate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
if len(set(nums)) == len(nums):
return False
d = {}
for i in range(len(nums)):
if nums[i] in d.keys() and i - d[nums[i]] <= k:
return True
else:
d[nums[i]] = i
return False
