LeetCode 532. K-diff Pairs in an Array
這題有好多種解法,不知道為何一堆人點爛就是。
題目
輸入一個整數陣列nums及正整數k,求滿足條件的數對(nums[i], nums[j])有多少個。
0 <= i < j < nums.length
|nums[i] - nums[j]| == k
解法
使用雜湊表計算各整數出現次數。
當k=0時,該數必須出現2次以上才能成對;k>0時,則檢查n+k是否存在。
class Solution:
def findPairs(self, nums: List[int], k: int) -> int:
ctr=Counter(nums)
ans=0
for n in ctr:
if k==0 and ctr[n]>1 or k>0 and (n+k) in ctr:
ans+=1
return ans
排序後,使用雙指標。
j必須保持在i之後,若j被i趕上或是nums[i]+k超過nums[j]時,j往後移動。
且必須去重複,題目只要求數對而不是指針,當nums[i]與nums[i-1]相同時,直接跳過,或是nums[i]+k不足nums[j]時,i往後移動。
若不滿足以上條件,則代表nums[i]+k=nums[j]了,答案+1,把i,j都往後移動。
class Solution:
def findPairs(self, nums: List[int], k: int) -> int:
N = len(nums)
nums.sort()
ans = i = j = 0
while i < N and j < N:
if j <= i or nums[i]+k > nums[j]:
j += 1
elif i > 0 and nums[i] == nums[i-1] or nums[i]+k < nums[j]:
i += 1
else:
ans += 1
i += 1
j += 1
return ans
其實也可以用二分搜解決,程式碼就不附上了。
排序後,每個nums[i],對i+1~N-1找nums[i]+k值,找到就更新答案。一樣要去重複,如果nums[i]=nums[i-1]則跳過。