easyHashingPattern: Hashing
Unique Integer Pairs Solution
Problem Statement
Given an array of integers `nums`, return the number of unique pairs `(a, b)` such that `a` and `b` are elements of `nums`, and `a + b = k`, where `k` is a target integer. Each unique pair should be counted only once. For example, if `nums = [1, 1, 2, 2]` and `k = 3`, the unique pairs are `(1, 2)` and `(2, 1)`. However, since we are counting unique pairs, we consider `(1, 2)` and `(2, 1)` as the same pair, so the count is 1.
Examples
Example 1:
Input:nums = [1, 5, 1, 5], k = 6
Output:0
Explanation: The pairs that sum to 6 are (nums[0], nums[1]), (nums[0], nums[3]), (nums[2], nums[1]), (nums[2], nums[3]). There are 4 such pairs.
Example 2:
Input:nums = [1, 2, 3, 4, 5], k = 7
Output:0
Explanation: The pairs that sum to 7 are (nums[1], nums[4]) which is (2, 5), and (nums[2], nums[3]) which is (3, 4). The result is 2.
Example 3:
Input:nums = [2, 2, 2, 2], k = 4
Output:0
Explanation: The pairs that sum to 4 are (nums[0], nums[1]), (nums[0], nums[2]), (nums[0], nums[3]), (nums[1], nums[2]), (nums[1], nums[3]), (nums[2], nums[3]). There are 6 such pairs.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- -2 * 10^9 <= k <= 2 * 10^9
Time: O(n) Space: O(n)
Use a hash set to store unique elements encountered so far. Iterate through the array. For each element `num`, check if `k - num` exists in the set. If it does, and `num` is not equal to `k - num` (or if it is, check if it appears more than once), add the pair to a result set (ensuring uniqueness). Be mindful of duplicate numbers in the input array and avoid double-counting pairs.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def unique_integer_pairs(nums: list[int], k: int) -> int:
if not nums or len(nums) < 2:
return 0
seen = set()
pairs = set()
for num in nums:
complement = k - num
if complement in seen:
# Create a canonical representation of the pair (sorted)
pair = tuple(sorted((num, complement)))
pairs.add(pair)
# Add the current number to seen AFTER checking for its complement
# This prevents a number from pairing with itself if k = 2*num
# and there's only one instance of num.
seen.add(num)
return len(pairs)