一、題目描述

題目內(nèi)容：

題目示例：

題目解析：

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

二、思路分析

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

• nums數(shù)組元素都是整數(shù)
• 索引位置i與位置j,不能相等
• k-diff數(shù)對關(guān)系：nums[i] - nums[j] = k -> nums[i] = nums[j] + k -〉 nums[i] - k = nums[j]
• k-diff數(shù)對，存在相同數(shù)對情況，但結(jié)果只取1次

因此，我們的對題目中進(jìn)行詳細(xì)了解了，因為會排除重復(fù)的數(shù)對，我們很容易想哈希表來構(gòu)建

方法一：構(gòu)建哈希表

根據(jù)上述思路，我們使用python代碼能快速實現(xiàn)，代碼如下：

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)

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

方法二：雙指針

根據(jù)上述思路，使用python代碼實現(xiàn)，代碼如下：

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

• 首先對nums數(shù)組中的元素按照從低到高的順序排列
• 在遞增的數(shù)組中，由于雙指針 i!=j，因此i指針一定是小于j的
• 枚舉查找的判斷的條件 nums[j] < nums[i]+k,指針j則往后移動
• 當(dāng)nums[j] = nums[i] + k 時，則對數(shù)次數(shù)+1

三、總結(jié)

本題可以使用哈希方法要使用兩個哈希表，屬于犧牲空間換取效率。雙指針方法，雖然沒有用額外的空間，但是速度較于方法一慢一點。

我們用第一種方法，AC提交記錄如下：

• 時間復(fù)雜度O(n),n為nums長度
• 空間復(fù)雜度O(n),需要使用哈希表，n為nums長度

到此這篇關(guān)于python數(shù)組中的 k-diff 數(shù)對例題解析的文章就介紹到這了,更多相關(guān)python k-diff 內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論