Question

16.24. Pairs With Sum

Description

Design an algorithm to find all pairs of integers within an array which sum to a specified value.

Example 1:

Input: nums = [5,6,5], target = 11

Output: [[5,6]]

Example 2:

Input: nums = [5,6,5,6], target = 11

Output: [[5,6],[5,6]]

Note:

• nums.length <= 100000

Solutions

Solution 1: Hash Table

We can use a hash table to store the elements in the array, with the keys being the elements in the array and the values being the number of times the element appears.

We traverse the array, and for each element $x$, we calculate $y = target - x$. If $y$ exists in the hash table, it means that there is a pair of numbers $(x, y)$ that add up to the target, and we add it to the answer and reduce the count of $y$ by $1$. If $y$ does not exist in the hash table, it means that there is no such pair of numbers, and we increase the count of $x$ by $1$.

After the traversal, we can obtain the answer.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array.

class Solution:
  def pairSums(self, nums: List[int], target: int) -> List[List[int]]:
    cnt = Counter()
    ans = []
    for x in nums:
      y = target - x
      if cnt[y]:
        cnt[y] -= 1
        ans.append([x, y])
      else:
        cnt[x] += 1
    return ans

class Solution {
  public List<List<Integer>> pairSums(int[] nums, int target) {
    Map<Integer, Integer> cnt = new HashMap<>();
    List<List<Integer>> ans = new ArrayList<>();
    for (int x : nums) {
      int y = target - x;
      if (cnt.containsKey(y)) {
        ans.add(List.of(x, y));
        if (cnt.merge(y, -1, Integer::sum) == 0) {
          cnt.remove(y);
        }
      } else {
        cnt.merge(x, 1, Integer::sum);
      }
    }
    return ans;
  }
}

class Solution {
public:
  vector<vector<int>> pairSums(vector<int>& nums, int target) {
    unordered_map<int, int> cnt;
    vector<vector<int>> ans;
    for (int x : nums) {
      int y = target - x;
      if (cnt[y]) {
        --cnt[y];
        ans.push_back({x, y});
      } else {
        ++cnt[x];
      }
    }
    return ans;
  }
};

func pairSums(nums []int, target int) (ans [][]int) {
  cnt := map[int]int{}
  for _, x := range nums {
    y := target - x
    if cnt[y] > 0 {
      cnt[y]--
      ans = append(ans, []int{x, y})
    } else {
      cnt[x]++
    }
  }
  return
}

function pairSums(nums: number[], target: number): number[][] {
  const cnt = new Map();
  const ans: number[][] = [];
  for (const x of nums) {
    const y = target - x;
    if (cnt.has(y)) {
      ans.push([x, y]);
      const yCount = cnt.get(y) - 1;
      if (yCount === 0) {
        cnt.delete(y);
      } else {
        cnt.set(y, yCount);
      }
    } else {
      cnt.set(x, (cnt.get(x) || 0) + 1);
    }
  }
  return ans;
}