Leetcode-532的解题过程。

• 题目

  Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.
  Example 1:
  Input: [3, 1, 4, 1, 5], k = 2
  Output: 2
  Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
  Although we have two 1s in the input, we should only return the number of unique pairs.
  Example 2:
  Input:[1, 2, 3, 4, 5], k = 1
  Output: 4
  Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).
  Example 3:
  Input: [1, 3, 1, 5, 4], k = 0
  Output: 1
  Explanation: There is one 0-diff pair in the array, (1, 1).
  Note:

  1. The pairs (i, j) and (j, i) count as the same pair.
  2. The length of the array won’t exceed 10,000.
  3. All the integers in the given input belong to the range: [-1e7, 1e7].

• 解析

  Easy题，大意是在一个数组中统计相差为k的元素对的个数。暴搜的时间复杂度是$O(n^2)$，不可取。比较容易想到的是先对数组排序，在升序数组中用前后两个指针遍历。如果两个指针对应的元素之差小于k，则后面指针前进一步，反之前面指针前进一步，刚好等于k则找到一个符合条件的元素对，同时后面指针前进一步。可以把时间复杂度降到$O(n\log{n})$。整体思路不难，需要注意的是待统计的元素对是不讲顺序的，并且同样的元素对只计算一次。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

  class Solution(object): def findPairs(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ if len(nums)<2: return 0 nums = sorted(nums) first = nums[0] pairs = set() j=0 for i in range(1,len(nums)): if nums[i]-first>=k: j=i break else: return 0 i=0 while i<len(nums) and j < len(nums): if nums[j]-nums[i]<k: j+=1 continue elif nums[j]-nums[i]==k: pairs.add((nums[i],nums[j])) j+=1 continue else: i+=1 if i==j: j+=1 return len(pairs)