腳本之家服務(wù)器常用軟件

快捷導(dǎo)航

軟件下載

android MAC 驅(qū)動(dòng)下載字體下載 DLL

源碼下載

PHP ASP.NET ASP JSP

軟件編程

C# JAVA C 語(yǔ)言 Delphi Android

網(wǎng)絡(luò)編程

PHP ASP.NET ASP JavaScript

在線工具

CSS格式化 JS格式化 Html轉(zhuǎn)化為Js

數(shù)據(jù)庫(kù)

MYSQL MSSQL oracle DB2 MARIADB

CMS

PHPCMS DEDECMS 帝國(guó)CMS WordPress

常用工具

PHP開(kāi)發(fā)工具 python Photoshop 必備軟件

python數(shù)組中的?k-diff?數(shù)對(duì)例題解析

更新時(shí)間：2022年06月17日 10:00:40 作者：??盆友圈的小可愛(ài)????

這篇文章主要介紹了python數(shù)組中的?k-diff?數(shù)對(duì)例題解析，文章根據(jù)題目?jī)?nèi)容對(duì)其進(jìn)行分析以此展開(kāi)主題內(nèi)容，感興趣的小伙伴可以參考一下下面文章詳情

一、題目描述

題目?jī)?nèi)容：

題目示例：

題目解析：

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

二、思路分析

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

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

因此，我們的對(duì)題目中進(jìn)行詳細(xì)了解了，因?yàn)闀?huì)排除重復(fù)的數(shù)對(duì)，我們很容易想哈希表來(lái)構(gòu)建

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

根據(jù)上述思路，我們使用python代碼能快速實(shí)現(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ù)對(duì)中重復(fù)場(chǎng)景如示例一中差值為k=1,(1,3) & (3,1)視為一種情況，則要定義兩個(gè)哈希表來(lái)儲(chǔ)存
哈希表可以通過(guò)字典k-value或者集合set(),本題無(wú)需考慮索引關(guān)系定義ans,numset兩個(gè)集合
當(dāng) nums[i] > nums[j],則nums[j] = nums[i] - k在numset中，取最小的那一個(gè)則ans.add(nums[i]-k),
當(dāng) nuns[i] < nums[j],則nums[j] = nums[i] + k 在numset中，取較小的那一個(gè)則ans.add(nums[i])

方法二：雙指針

根據(jù)上述思路，使用python代碼實(shí)現(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