一、題目描述

給定一個整數數組和一個整數 k, 你需要在數組里找到不同的 k-diff 數對。這里將 k-diff 數對定義為一個整數對 (i, j), 其中 i 和 j 都是數組中的數字，且兩數之差的絕對值是 k。

示例 1:

• 輸入: [3, 1, 4, 1, 5], k = 2
• 輸出: 2

解釋: 數組中有兩個 2-diff 數對, (1, 3) 和 (3, 5)。盡管數組中有兩個 1，但我們只應返回不同的數對的數量。

二、解題思路

利用兩個數的絕對值之差為 k 的關系 x - y = k，推出 y = x - k 和 x = y + k：

• saw 集合保存訪問過的元素
• diff 集合保存已找到的 k-diff 數對中的較小值
• 遍歷所有元素，判斷當前元素是否符合下面 2 個條件之一
• 如果 y = x - k (1 = 3 - 2) 在 saw 中，則在 diff 中加入較小值 x - k = 1
• 如果 x = y + k (3 = 1 + 2)在 saw 中，則在 diff 中加入較小值 y = 1
• 在 saw 中加入已訪問的元素
• 放回 diff 集合的大小（set 相同的元素只存放一次）

要注意 set 中相同的元素只存放一次，所以對于 3 1 4 1 5 的情況，diff 集合中只會保存 1 個元素 1，表示只有一個 (1, 3) 數對。

class Solution {
public:
  int findPairs(vector<int>& nums, int k) {
    if (k < 0)
      return 0;

    // 保存訪問的元素
    std::set<int> saw;

    // 保存 k-diff 數對中較小的那個
    // 也可以保存較大的，只用來統計數對個數
    std::set<int> diff;

    for (int i = 0; i < nums.size(); i++) {
      // 檢查數對中較小的數 1 是否在數組中：3 - 2 = 1
      if (saw.find(nums[i] - k) != saw.end())
        diff.insert(nums[i] - k); // 插入數對中較小的數 1

      // 檢查數對中較大的數 3 是否在數組中：1 + 2 = 3
      if (saw.find(nums[i] + k) != saw.end())
        diff.insert(nums[i]); // 插入數對中較小的數 1

      saw.insert(nums[i]);
    }

    // 因為 set 中不存在重復元素
    // 所以不同的元素個數代表不同的 k-diff 數對個數
    return diff.size();
  }
};

復雜度分析

• 時間復雜度：O(n)，只需要遍歷一次數組
• 空間復雜度：O(n)，set 集合空間與數組大小 n 呈線性增長