【Leetcode_总结】532. 数组中的K-diff数对 - python

链接：https://leetcode-cn.com/problems/k-diff-pairs-in-an-array/description/

Q：

给定一个整数数组和一个整数 k, 你需要在数组里找到不同的 k-diff 数对。这里将 k-diff 数对定义为一个整数对 (i, j), 其中 i 和 j 都是数组中的数字，且两数之差的绝对值是 k.

示例 1:

输入: [3, 1, 4, 1, 5], k = 2
输出: 2
解释: 数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。
尽管数组中有两个1，但我们只应返回不同的数对的数量。

---

思路：k小于0 返回0； 等于0 返回数组中重复的值数量 ；大于0计算能够使得相减等于k的数量 第一次使用list超时 换为字典后通过 但是效率很低

超时： 

class Solution(object):
    def findPairs(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        if k == 0:
            res = 0
            temp = list(set(nums))
            for t in temp:
                if nums.count(t) > 1:
                    res += 1
            return res
        if k > 0:
            res = 0
            temp = []
            for i in range(len(nums)):
                if nums[i] + k in nums and nums[i] not in temp :
                    res += 1
                    temp.append(nums[i])
            return res
        if k < 0:
            res = 0
            return res

通过： 

class Solution(object):
    def findPairs(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        if k < 0:
            return 0
        dict4nums = {}
        for i in range(len(nums)):
            if nums[i] in dict4nums:
                dict4nums[nums[i]] += 1
            else:
                dict4nums[nums[i]] = 1
        if k == 0:
            res = 0
            for value in dict4nums:
                if dict4nums[value] > 1:
                    res += 1
            return res
        if k > 0:
            res = 0
            temp = []
            for i in range(len(nums)):
                if nums[i] + k in dict4nums and nums[i] not in temp:
                    res += 1
                    temp.append(nums[i])
            return res

稍微改一下：

class Solution(object):
    def findPairs(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        if k < 0:
            return 0
        dict4nums = {}
        for i in range(len(nums)):
            if nums[i] in dict4nums:
                dict4nums[nums[i]] += 1
            else:
                dict4nums[nums[i]] = 1
        if k == 0:
            res = 0
            for value in dict4nums:
                if dict4nums[value] > 1:
                    res += 1
            return res
        if k > 0:
            res = 0
            temp = list(set(nums))
            for i in range(len(temp)):
                if temp[i] + k in dict4nums:
                    res += 1
            return res