這是悅樂書的第254次更新，第267篇原創

01 看題和準備

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

輸入：[3,1,4,1,5]，k = 2
輸出：2
說明：數組中有兩個2-diff對，（1,3）和（3,5）。雖然我們在輸入中有兩個1，但我們應該只返回唯一對的數量。

輸入：[1,2,3,4,5]，k = 1
輸出：4
說明：數組中有四個1-diff對，（1,2），（2,3），（3,4）和（4,5）。

輸入：[1,3,1,5,4]，k = 0
輸出：1
說明：數組中有一個0-diff對，（1,1）。

注意：

• 對（i，j）和（j，i）計為同一對。

• 數組的長度不會超過10,000。

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

本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。

02 第一種解法

暴力解法。先排序，然后使用兩層循環，計算不同元素的絕對值，如果等于k，次數就加1。在外面第一層循環那里，如果前后元素相同，就跳過當前循環，進行下一次循環。在內層循環那里同樣做了類似的判斷，排除重復計算。

此解法的時間復雜度是O(n^2)，空間復雜度是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 第二種解法

第一種解法時間復雜度太高了，得降低點。第一種解法，我們是做減法，求絕對值，來判斷是否等于k，我們也可以做加法，拿當前元素加上k，然后看新元素是否存在于數組中。同時還要考慮重復的計算數據，因此參與計算的元素是唯一的，對此我們可以使用HashMap，已元素值作為key，該元素值出現次數為value。遍歷key，如果key加上k后的值存在于map中，次數加1，另外如果k為0的時候，只需要判斷每個key所對應的value是否大于等于2即可。

此解法的時間復雜度是O(n)，最壞情況也可能是O(n^2)，空間復雜度是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 第三種解法

對于第二種解法，還可以將判斷放在循環體里面。

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時，對數組進行遍歷，如果當前元素不存在于set1中，就添加進set1，如果存在set1中，就去判斷是否存在于set2中，如果不存在，次數就加1，并將元素添加進set2中。

如果k不等于0，遍歷數組，將當前元素添加進set1，將當前元素加上k后再添加進set2，然后使用retainAll方法，將set1中不包含set2元素的元素剔除掉（也就是兩set的交集），最后count等于set1中元素的個數。

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 第五種解法

使用雙指針。還是先將數據排序，定義左右兩個指針，分別從0開始，如果左右指針相等，說明是循環的第一次或者重復了，就需要將右指針往后移動一位。如果左指針所指向元素加上k后等于右指針的元素，那么次數加1，接著要判斷，如果右指針所指向位置后面的元素和當前元素相等，那么右指針繼續往后移動。如果左指針所指向元素加上k后小于右指針的元素，說明左邊的元素小了，左指針向前移動。如果左指針所指向元素加上k后大于右指針的元素，說明右邊的元素小了，右指針向前移動。

此解法的時間復雜度是O(n log(n))，空間復雜度是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 小結

此題的測試用例中，k出現了負值，所以在特殊情況判斷中，還需要判斷k小于0，這也是本題不嚴謹的一個地方。

算法專題目前已日更超過三個月，算法題文章121+篇，公眾號對話框回復【數據結構與算法】、【算法】、【數據結構】中的任一關鍵詞，獲取系列文章合集。

以上就是全部內容，如果大家有什么好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支持！

轉載于:https://www.cnblogs.com/xiaochuan94/p/10399011.html

總結

以上是生活随笔為你收集整理的LeetCode算法题-K-diff Pairs in an Array（Java实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。