Solution: Find Two Pairs in an Array Such That a+b = c+d

Statement

Given an array of distinct integers, nums, determine whether there exist two pairs, $(a, b)$ and $(c, d)$, such that $a + b = c + d$, where $a$, $b$, $c$, and $d$ are unique elements within the array. If there are multiple solutions, return any one of them.

Constraints:

• $4 \leq$ nums.length $\leq 10^3$

• $-10^3 \leq$ nums[i] $\leq 10^3$

Solution

In this solution, we identify pairs of numbers with matching sums by utilizing a map to remember the sums and its associated pairs. By storing each unique sum as a key and the corresponding pair as its value, the algorithm can quickly check if a previously encountered sum matches the sum of a current pair. This enables the identification of two distinct pairs that add up to the same sum.

Let’s walk through the following steps of the solution:

• Initializes an empty map to store the sum of pairs.

• Iterate over each pair of numbers in nums and calculate their sum. Check whether this sum has already been encountered and stored in the map:

  • If yes, return the two pairs that add up to this sum: the one previously stored and the current one.

  • Otherwise, add the sum as key and its pair as the corresponding value in the map for future reference.

• Return NULL, if no such pairs are found by the end of the iteration.

Let’s look at the illustration below to better understand the solution: