Pair Sums

ArrayHash TableTwo Pointers

Given an array of integers and a target sum, find all unique pairs of numbers that sum up to the given target. Return these pairs as an array of arrays, each pair sorted in non-decreasing order.

Example:

Input: numbers = [1, 2, 3, 4, 5], target = 5 Output: [[1, 4], [2, 3]]

Example 1

Input

Output

[[1, 4], [2, 3]]

Explanation. There are two unique pairs that sum up to the target 5: pairs (1,4) and (2,3).

Example 2

Input

[
  [
    -1,
    0,
    1,
    2,
    -1,
    -4
  ],
  0
]

Output

[[-1, 1]]

Explanation. There is one unique pair that sums up to the target 0: pair (-1,1).

Example 3

Input

Output

[[0, 0]]

Explanation. The pair (0, 0) is repeated multiple times but only one unique pair should be returned.

Follow-up: How would the solution change if the input array is sorted? Discuss the implications of sorted data on your algorithm.

Constraints:

The input array may contain duplicated values but the output array must contain only unique pairs.

Views: 3