217. Contains Duplicate & 219. Contains Duplicate II

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    
        
        
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容