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
用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.