FastPrepThree Sum: Unique Target Triplets

Three Sum: Unique Target Triplets

Google logoGoogle● MediumINTERNONSITE INTERVIEW
Learn

Problem statement

Given an integer array nums and an integer target, return every distinct value triplet whose sum equals target.

  • Each triplet must be nondecreasing.
  • The returned list must contain no duplicate value triplets.
  • Return the triplets in lexicographic order.

You may reorder nums. Use 64-bit arithmetic for every three-value sum. The target complexity is O(n^2) time and O(1) auxiliary space, excluding the returned triplets and the sorting implementation's call stack.

Large-input follow-up

If the array cannot fit in memory, discuss how external sorting can produce an on-disk ordered sequence and how buffered scans trade additional I/O for bounded memory.

Function

threeSumTarget(nums: int[], target: int) → int[][]

Examples

Example 1

nums = [-1,0,1,2,-1,-4]target = 0return = [[-1,-1,2],[-1,0,1]]

The two distinct value triplets whose sum is 0 are [-1,-1,2] and [-1,0,1].

Example 2

nums = [2,2,2,2]target = 6return = [[2,2,2]]

Many index triples exist, but they all produce the same value triplet, so [2,2,2] appears once.

Example 3

nums = [1,2,3,4,5,0,-1]target = 6return = [[-1,2,5],[-1,3,4],[0,1,5],[0,2,4],[1,2,3]]

These are all five nondecreasing value triplets whose sum is 6, listed in lexicographic order.

Example 4

nums = [1,2,4,8]target = 100return = []

No three values sum to 100.

Constraints

  • 3 <= nums.length <= 3000.
  • -10^9 <= nums[i] <= 10^9.
  • -10^9 <= target <= 10^9.

More Google problems

See Google hiring insights
public int[][] threeSumTarget(int[] nums, int target) {
  // Write your code here.
}
nums[-1,0,1,2,-1,-4]
target0
expected[[-1,-1,2],[-1,0,1]]
Checking account…