107 - 532数组中的k-diff数对

题目

给定一个整数数组和一个整数 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，但我们只应返回不同的数对的数量。

示例 2:

输入:[1, 2, 3, 4, 5], k = 1 输出: 4 解释: 数组中有四个 1-diff 数对, (1, 2), (2, 3), (3, 4) 和 (4, 5)。

示例 3:

输入: [1, 3, 1, 5, 4], k = 0 输出: 1 解释: 数组中只有一个 0-diff 数对，(1, 1)。

注意:

1. 数对 (i, j) 和数对 (j, i) 被算作同一数对。

2. 数组的长度不超过10,000。

3. 所有输入的整数的范围在 [-1e7, 1e7]。

解答

这翻译的。。对中英文都不友好

意思大概是，2-diff是两个数相差为2。然后输出一共有多少对这样的组合。有点像两数之和

双指针，循环内移动指针

https://leetcode.com/problems/k-diff-pairs-in-an-array/discuss/100104/Two-pointer-Approach

先排序。内循环移动到差小于k的地方，如果正好是k则结果++。然后移动外循环跳过所有相同的值。

func max(i, j int) int {
    if i < j {
        return j
    }
    return i
}
func findPairs(nums []int, k int) int {
    if nums == nil || k < 0 || len(nums) < 2 {
        return 0
    }
    sort.Ints(nums)
    var ans int
    for i, j := 0, 0; i < len(nums); i++ {
        j := max(i+1, j)
        for j < len(nums) && nums[j]-nums[i] < k {
            j++
        }
        if j < len(nums) && nums[j]-nums[i] == k {
            ans++
        }
        for i+1 < len(nums) && nums[i] == nums[i+1] {
            i++
        }
    }
    return ans
}

Runtime: 20 ms, faster than 83.67% of Go online submissions for K-diff Pairs in an Array.

Memory Usage: 5.9 MB, less than 100.00% of Go online submissions for K-diff Pairs in an Array.

双指针，大循环移动指针

func findPairs(nums []int, k int) int {
    if nums == nil || k < 0 || len(nums) < 2 {
        return 0
    }
    sort.Ints(nums)
    var ans int
    for i, j := 0, 0; j < len(nums); {
        if j <= i || nums[i]+k > nums[j] {
            j++
        } else if i>0 && nums[i] == nums[i-1] || nums[i]+k < nums[j] {
            i++
        } else {
            ans++
            i++
        }
    }
    return ans
}

Runtime: 28 ms, faster than 39.80% of Go online submissions for K-diff Pairs in an Array.

Memory Usage: 5.9 MB, less than 100.00% of Go online submissions for K-diff Pairs in an Array.

这个思路是最容易理解的😂

func findPairs(nums []int, k int) int {
    if nums == nil || k < 0 || len(nums) < 2 {
        return 0
    }
    sort.Ints(nums)
    var ans int
    for i, j := 0, 0; i < len(nums) && j < len(nums); {
        if j <= i || nums[i]+k > nums[j] {
            j++
        } else if nums[i]+k < nums[j] {
            i++
        } else {
            ans++
            i++
            for j < len(nums)-1 && nums[j] == nums[j+1] {
                j++
            }
            j++
        }
    }
    return ans
}

Runtime: 20 ms, faster than 83.67% of Go online submissions for K-diff Pairs in an Array.

Memory Usage: 5.9 MB, less than 100.00% of Go online submissions for K-diff Pairs in an Array.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findPairs = function (nums, k) {
  if (!nums || k < 0 || nums.length < 2) {
    return 0
  }
  nums.sort((a, b) => a - b)
  let ans = 0
  for (let i = 0, j = 0; i < nums.length && j < nums.length;) {
    if (j <= i || nums[i] + k > nums[j]) {
      j++
    } else if (nums[i] + k < nums[j]) {
      i++
    } else {
      ans++
      i++
      while (j < nums.length - 1 && nums[j] === nums[j + 1]) {
        j++
      }
      j++
    }
  }
  return ans
};

Runtime: 92 ms, faster than 42.82% of JavaScript online submissions for K-diff Pairs in an Array.

Memory Usage: 37.2 MB, less than 100.00% of JavaScript online submissions for K-diff Pairs in an Array.

class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        if not nums or k < 0 or len(nums) < 2:
            return 0
        nums = sorted(nums)
        ans = 0
        i = 0
        j = 0
        while i < len(nums) and j < len(nums):
            if j <= i or nums[i] + k > nums[j]:
                j += 1
            elif nums[i] + k < nums[j]:
                i += 1
            else:
                ans += 1
                i += 1
                while j < len(nums) - 1 and nums[j] == nums[j + 1]:
                    j += 1
                j += 1
        return ans

Runtime: 176 ms, faster than 24.52% of Python3 online submissions for K-diff Pairs in an Array.

Memory Usage: 15.2 MB, less than 64.52% of Python3 online submissions for K-diff Pairs in an Array.

哈希

感觉go很适合这个hash方法，因为hash自带了set

作者：yybeta 链接：https://leetcode-cn.com/problems/k-diff-pairs-in-an-array/solution/ha-xi-onzui-jian-dan-jie-fa-by-mai-mai-mai-mai-zi/

用set来存大的那个数，当然也可以存小的那个

class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        if not nums or k < 0 or len(nums) < 2:
            return 0
        s, r = set(), set()
        for n in nums:
            if n + k in s:
                r.add(n + k)
            if n - k in s:
                r.add(n)
            s.add(n)
        return len(r)

Runtime: 156 ms, faster than 41.90% of Python3 online submissions for K-diff Pairs in an Array.

Memory Usage: 15.8 MB, less than 16.13% of Python3 online submissions for K-diff Pairs in an Array.

func findPairs(nums []int, k int) int {
    if nums == nil || k < 0 || len(nums) < 2 {
        return 0
    }
    s := make(map[int]bool)
    r := make(map[int]bool)
    for _, value := range nums {
        if _, ok := s[value+k]; ok {
            r[value+k] = true
        }
        if _, ok := s[value-k]; ok {
            r[value] = true
        }
        s[value] = true
    }
    return len(r)
}

Runtime: 20 ms, faster than 83.67% of Go online submissions for K-diff Pairs in an Array.

Memory Usage: 6.4 MB, less than 100.00% of Go online submissions for K-diff Pairs in an Array.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findPairs = function (nums, k) {
  if (!nums || k < 0 || nums.length < 2) {
    return 0
  }
  let s = new Set()
  let r = new Set()
  for (const num of nums) {
    if (s.has(num + k)) {
      r.add(num + k)
    }
    if (s.has(num - k)) {
      r.add(num)
    }
    s.add(num)
  }
  return r.size
};

Runtime: 84 ms, faster than 45.92% of JavaScript online submissions for K-diff Pairs in an Array.

Memory Usage: 39.1 MB, less than 100.00% of JavaScript online submissions for K-diff Pairs in an Array.