基于哈希表求解数组中差值为k的整数对查找与计数问题

Got it, let's work through this problem step by step. The goal is to find all unique integer pairs in a distinct-integer array where the difference is exactly k, and count how many such pairs exist—using only a hash table (or hash set, which is perfect for fast existence checks here).

核心思路 #

Since we're dealing with distinct integers, we can leverage a hash set to cut down lookup time to O(1). The key trick here is to avoid counting duplicate pairs (like (1,3) and (3,1) being treated as the same pair). We do this by only checking if num + k exists in the set for each element num—this way, each unordered pair is counted exactly once (we only look for the larger number in the pair relative to the current element).

Here's the breakdown:

• First, dump all elements of the array into a hash set. This lets us check if a number exists in constant time.
• Initialize a counter to keep track of valid pairs, and a list to store the pairs themselves.
• Iterate through each number in the original array:
  • For the current number num, check if num + k is present in the hash set.
  • If it is, increment the counter and add the pair (num, num + k) to our list.
• Return the counter and the list of pairs.

Note: If k is negative, we can just return 0 immediately—since a negative difference is equivalent to checking num - |k|, which would duplicate the positive k logic, and our approach already covers positive differences. Also, if k = 0, since all array elements are distinct, there are no valid pairs, so we return 0.

代码实现（Python） #

def find_k_diff_pairs(arr, k):
    # Handle edge case: negative k (since difference is absolute in practice)
    if k < 0:
        return 0, []
    # Convert array to a hash set for O(1) lookups
    num_set = set(arr)
    pair_count = 0
    valid_pairs = []
    
    for num in arr:
        target = num + k
        if target in num_set:
            valid_pairs.append((num, target))
            pair_count += 1
    
    return pair_count, valid_pairs

# Test with the example given
sample_arr = [1, 7, 5, 9, 2, 12, 3]
k_value = 2
count, pairs = find_k_diff_pairs(sample_arr, k_value)

print(f"Number of valid pairs: {count}")
print(f"Valid pairs: {pairs}")

运行结果验证 #

For the sample array {1, 7, 5, 9, 2, 12, 3} and k=2, the output will be:

Number of valid pairs: 4
Valid pairs: [(1, 3), (7, 9), (5, 7), (3, 5)]

These are all the unique pairs with a difference of 2—no duplicates, and we've correctly counted all valid combinations.

时间与空间复杂度 #

• Time Complexity: O(n), where n is the length of the array. We iterate through the array once, and each lookup in the hash set is O(1).
• Space Complexity: O(n), since we store all array elements in the hash set.

内容的提问来源于stack exchange，提问作者Rahul Raj