python陣列中的 k-diff 數對例題解析

2022-06-17 14:03:33

一、題目描述

題目內容：

題目範例：

題目解析：

1 <= nums.length <= 104
-107 <= nums[i] <= 107
0 <= k <= 107

二、思路分析

我們拿到本題，讀取題意要求在一組整數陣列中，求出差值為k的數對對數k-diff。在思考如何解答該題之前，需要明確如下幾點細節：

nums陣列元素都是整數
索引位置i與位置j,不能相等
k-diff數對關係：nums[i] - nums[j] = k -> nums[i] = nums[j] + k -〉 nums[i] - k = nums[j]
k-diff數對，存在相同數對情況，但結果只取1次

因此，我們的對題目中進行詳細瞭解了，因為會排除重複的數對，我們很容易想雜湊表來構建

方法一：構建雜湊表

根據上述思路，我們使用python程式碼能快速實現，程式碼如下：

class Solution(object):
    def findPairs(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        ans = set()
        numset = set()
        for num in nums:
            if num - k in numset:
                ans.add(num-k)
            if num + k in numset:
                ans.add(num)
            numset.add(num)
        return len(ans)

數對中重複場景如範例一中差值為k=1,(1,3) & (3,1)視為一種情況，則要定義兩個雜湊表來儲存
雜湊表可以通過字典k-value或者集合set(),本題無需考慮索引關係定義ans,numset兩個集合
當 nums[i] > nums[j],則nums[j] = nums[i] - k在numset中，取最小的那一個則ans.add(nums[i]-k),
當 nuns[i] < nums[j],則nums[j] = nums[i] + k 在numset中，取較小的那一個則ans.add(nums[i])

方法二：雙指標

根據上述思路，使用python程式碼實現，程式碼如下：

class Solution(object):
    def findPairs(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        nums.sort()
        ans = 0
        j = 0
        for i in range(len(nums)):
            if i == 0 or nums[i] != nums[i-1]:
                while j < len(nums) and (nums[j] < nums[i] + k or j <= i):
                    j +=1
                if j < len(nums) and nums[j] == nums[i] + k:
                    ans +=1
        return ans