Leetcode算法刷题：217和219题 Contains Duplicate

从题目名字就可以看出这两道题是相似的，219是217的加强版

217：Contains Duplicate

题目

给予一个数组，判断是否有重复的元素。如果有就返回True，没有就返回False。以下是我第一次想到的方法

解题思路

遍历这个数组，建立一个字典，存储每个不同的数字的出现次数。如果某个元素的出现次数大于1，则表示有重复

class Solution:

    # @param {integer[]} nums

    # @return {boolean}

    def containsDuplicate(self, nums):

		count = dict()

		for i in range(len(nums)):

			if nums[i] not in count:

				count[nums[i]] = 1

			else:

				count[nums[i]] += 1

		for i in count:

			if count[i] == 1:

				pass

			else:

				return True

		return False

这是我开始的解法，提交时间是82ms。提交后我马上想到了个更快的方法：用set消除冗余, 提交时间55ms，快了很多~

class Solution:

    # @param {integer[]} nums

    # @return {boolean}

    def containsDuplicate(self, nums):

        temp = len(nums)

        s = set(nums)

        if temp == len(s):

            return False

        return True

219: Contains Duplicate II

题目

给予一个数组和一个数字k，判断在这个数组中是否只有一对元素重复，且中间相隔的元素数目不超过k

解题思路

大致思路和217的第一种方法一样，不同的是上一题的字典存储的是元素: 出现次数, 而这时候存储的是元素：[出现次数, 相隔元素个数, 是否有重复元素(布尔值)]

class Solution:

    # @param {integer[]} nums

    # @param {integer} k

    # @return {boolean}

    def containsNearbyDuplicate(self, nums, k):

        count = dict()

        temp = 0

        for i in range(len(nums)):

            if nums[i] not in count:

                count[nums[i]] = [1, i, False]

            else:

                count[nums[i]] = [count[nums[i]][0] + 1, i - count[nums[i]][1], True]

        for i in count:

            if count[i][2]:

                temp += 1

        if temp > 1 or temp == 0:

            return False

        for i in count:

            if count[i][1] <= k and count[i][2]:

                return True

        return False