Two Pointers Pointers from both ends
156. 4Sum
You are given an array of integers nums and an integer target. Return every quadruple of values from
nums that adds up to target. A quadruple is four elements at four different positions, and you return
their values as a list of four numbers.
Return each quadruple once. Two quadruples are the same when they hold the same four values, even if the
values come from different positions or are listed in a different order. A value can appear in a quadruple
as many times as it appears in nums, and no more.
The quadruples can come back in any order, and so can the values inside each quadruple. The examples list each quadruple's values from smallest to largest and sort the quadruples.
Example 1
Input: nums = [3, -2, 1, 0, -1, 2, 3], target = 3
[[-2,-1,3,3],[-2,0,2,3],[-1,0,1,3]]Explanation: Three quadruples add up to 3: −2 + (−1) + 3 + 3, −2 + 0 + 2 + 3 and −1 + 0 + 1 + 3. The value 3 appears twice, so −2, 0, 2, 3 can be picked from two sets of positions, but it is listed once.
Example 2
Input: nums = [-2, -2, -2, -2, -2, 1], target = -8
[[-2,-2,-2,-2]]Explanation: There are five ways to pick four of the five −2s. They all hold the same values, so the quadruple is listed once.
Example 3
Input: nums = [1000000000, 1000000000, 1000000000, -1000000000, 0]
target = 1000000000
[[-1000000000,0,1000000000,1000000000]]Explanation: −109 + 0 + 109 + 109 = 109. Other quadruples add up to 2 × 109 and 3 × 109, which are past the range of a 32-bit integer.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 200-109 ≤ nums[i] ≤ 109-109 ≤ target ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.