這是悅樂書的第254次更新反番，第267篇原創(chuàng)

01 看題和準(zhǔn)備

今天介紹的是LeetCode算法題中Easy級別的第121題（順位題號是532）。給定一個整數(shù)數(shù)組和一個整數(shù)k为肮，您需要找到數(shù)組中唯一的k-diff對的數(shù)量摊册。 這里k-diff對被定義為整數(shù)對（i，j）颊艳，其中i和j都是數(shù)組中的數(shù)字茅特，它們的絕對差是k。例如：

輸入：[3,1,4,1,5]棋枕，k = 2
輸出：2
說明：數(shù)組中有兩個2-diff對白修，（1,3）和（3,5）。雖然我們在輸入中有兩個1重斑，但我們應(yīng)該只返回唯一對的數(shù)量兵睛。

輸入：[1,2,3,4,5]，k = 1
輸出：4
說明：數(shù)組中有四個1-diff對窥浪，（1,2）祖很，（2,3），（3,4）和（4,5）漾脂。

輸入：[1,3,1,5,4]假颇，k = 0
輸出：1
說明：數(shù)組中有一個0-diff對，（1,1）符相。

注意：

• 對（i拆融，j）和（j，i）計為同一對啊终。

• 數(shù)組的長度不會超過10,000镜豹。

• 給定輸入中的所有整數(shù)都屬于以下范圍：[-1e7, 1e7]。

本次解題使用的開發(fā)工具是eclipse蓝牲，jdk使用的版本是1.8趟脂，環(huán)境是win7 64位系統(tǒng)，使用Java語言編寫和測試例衍。

02 第一種解法

暴力解法昔期。先排序已卸，然后使用兩層循環(huán)，計算不同元素的絕對值硼一，如果等于k累澡，次數(shù)就加1。在外面第一層循環(huán)那里般贼，如果前后元素相同愧哟，就跳過當(dāng)前循環(huán)，進行下一次循環(huán)哼蛆。在內(nèi)層循環(huán)那里同樣做了類似的判斷蕊梧，排除重復(fù)計算。

此解法的時間復(fù)雜度是O(n^2)腮介，空間復(fù)雜度是O(1)肥矢。

public int findPairs(int[] nums, int k) {
    if (nums == null || nums.length == 0 || k < 0) {
        return 0;
    }
    Arrays.sort(nums);
    int count = 0;
    for (int i=0; i<nums.length; i++) {
        int n = nums[i];
        if (i >= 1 && nums[i-1] == nums[i]) {
            continue;
        }
        for (int j=i+1; j<nums.length; j++) {
            if (j >= i+2 && nums[j-1] == nums[j]) {
                continue;
            }
            if (Math.abs(n - nums[j]) == k) {
                count++;
            }
        }
    }
    return count;
}

03 第二種解法

第一種解法時間復(fù)雜度太高了，得降低點叠洗。第一種解法甘改，我們是做減法，求絕對值惕味，來判斷是否等于k楼誓，我們也可以做加法，拿當(dāng)前元素加上k名挥，然后看新元素是否存在于數(shù)組中疟羹。同時還要考慮重復(fù)的計算數(shù)據(jù)，因此參與計算的元素是唯一的禀倔，對此我們可以使用HashMap榄融，已元素值作為key，該元素值出現(xiàn)次數(shù)為value救湖。遍歷key愧杯，如果key加上k后的值存在于map中，次數(shù)加1鞋既，另外如果k為0的時候力九，只需要判斷每個key所對應(yīng)的value是否大于等于2即可。

此解法的時間復(fù)雜度是O(n)邑闺，最壞情況也可能是O(n^2)跌前，空間復(fù)雜度是O(n)。

public int findPairs2(int[] nums, int k) {
    if (nums == null || nums.length == 0 || k < 0) {
        return 0;
    }
    Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    for (int n : nums) {
        map.put(n, map.getOrDefault(n, 0)+1);
    }
    int count = 0;
    if (k == 0) {
        for (Integer key: map.keySet()) {
            if (map.get(key) >= 2) {
                count++;
            }
        }
    } else {
        for (Integer key: map.keySet()) {
            if (map.containsKey(key+k)) {
                count++;
            }
        }
    }
    return count;
}

04 第三種解法

對于第二種解法陡舅，還可以將判斷放在循環(huán)體里面抵乓。

public int findPairs3(int[] nums, int k) {
    if (nums == null || nums.length == 0 || k < 0) {
        return 0;
    }
    Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    for (int n : nums) {
        map.put(n, map.getOrDefault(n, 0)+1);
    }
    int count = 0;
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        if (k == 0) {
            if (entry.getValue() >= 2) {
                count++;
            } 
        } else {
            if (map.containsKey(entry.getKey()+k)) {
                count++;
            }
        }
    }
    return count; 
}

05 第四種解法

使用HashSet。使用兩個HashSet，同樣分為兩種情況：k等于0和K不等于0灾炭。

如果k等于0時茎芋，對數(shù)組進行遍歷，如果當(dāng)前元素不存在于set1中蜈出，就添加進set1田弥，如果存在set1中，就去判斷是否存在于set2中掏缎，如果不存在皱蹦，次數(shù)就加1，并將元素添加進set2中眷蜈。

如果k不等于0，遍歷數(shù)組沈自，將當(dāng)前元素添加進set1酌儒，將當(dāng)前元素加上k后再添加進set2，然后使用retainAll方法枯途，將set1中不包含set2元素的元素剔除掉（也就是兩set的交集）忌怎，最后count等于set1中元素的個數(shù)。

public int findPairs4(int[] nums, int k) {
    if (nums == null || nums.length == 0 || k < 0) {
        return 0;
    }
    Set<Integer> set1 = new HashSet<Integer>();
    Set<Integer> set2 = new HashSet<Integer>();
    int count = 0;
    if (k == 0) {
        for (int n : nums) {
            if (!set1.contains(n)) {
                set1.add(n);
            } else {
                if (!set2.contains(n)){
                    count++;
                }
                set2.add(n);
            }
        }
    } else {
        for (int n : nums) {
            set1.add(n);
            set2.add(n + k);
        }
        set1.retainAll(set2);
        count = set1.size();
    }
    return count;
}

06 第五種解法

使用雙指針酪夷。還是先將數(shù)據(jù)排序榴啸，定義左右兩個指針，分別從0開始晚岭，如果左右指針相等鸥印，說明是循環(huán)的第一次或者重復(fù)了，就需要將右指針往后移動一位坦报。如果左指針?biāo)赶蛟丶由蟢后等于右指針的元素库说，那么次數(shù)加1，接著要判斷片择，如果右指針?biāo)赶蛭恢煤竺娴脑睾彤?dāng)前元素相等潜的，那么右指針繼續(xù)往后移動。如果左指針?biāo)赶蛟丶由蟢后小于右指針的元素字管，說明左邊的元素小了啰挪，左指針向前移動。如果左指針?biāo)赶蛟丶由蟢后大于右指針的元素嘲叔，說明右邊的元素小了亡呵，右指針向前移動。

此解法的時間復(fù)雜度是O(n log(n))借跪，空間復(fù)雜度是O(1)政己。

public int findPairs5(int[] nums, int k) {
    if (nums == null || nums.length == 0 || k < 0) {
        return 0;
    }
    Arrays.sort(nums);
    int count = 0;
    int start = 0, end = 0;
    while (end < nums.length) {
        if (start == end) {
            end++;
        } else if (nums[start] + k == nums[end]) {
            count++;
            while (end + 1 < nums.length && nums[end] == nums[end + 1]) {
                end++;
            }
            end++;
        } else if (nums[start] + k < nums[end]) {
            start++;
        } else if (nums[start] + k > nums[end]) {
            end++;
        }
    }
    return count;
}

07 小結(jié)

此題的測試用例中，k出現(xiàn)了負(fù)值，所以在特殊情況判斷中歇由，還需要判斷k小于0卵牍，這也是本題不嚴(yán)謹(jǐn)?shù)囊粋€地方。

算法專題目前已日更超過三個月沦泌，算法題文章121+篇糊昙，公眾號對話框回復(fù)【數(shù)據(jù)結(jié)構(gòu)與算法】、【算法】谢谦、【數(shù)據(jù)結(jié)構(gòu)】中的任一關(guān)鍵詞释牺，獲取系列文章合集。

以上就是全部內(nèi)容回挽，如果大家有什么好的解法思路没咙、建議或者其他問題，可以下方留言交流千劈，點贊祭刚、留言、轉(zhuǎn)發(fā)就是對我最大的回報和支持墙牌！