Return Unique Three-Sum Value Triples

Return Unique Three-Sum Value Triples

Problem

Implement threeSumTarget(nums, target) -> triples.

Return every distinct value triple [a, b, c] for which three distinct input indices exist, a <= b <= c, and a + b + c == target.

Each value triple must appear exactly once even when the input contains duplicates. Sort the returned triples lexicographically. Return [] when no triple exists, and do not mutate nums.

Constraints

• 0 <= nums.length <= 2,000.
• -1,000,000,000 <= nums[i], target <= 1,000,000,000.
• Use signed 64-bit arithmetic for sums.
• Target O(n^2 + P) time after sorting, where P is the number of returned triples, and O(n + P) space including the result.

Examples

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

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

nums = [1, 2]
target = 3
triples = []

Discussion Requirements

• Explain how duplicate values are skipped without losing a valid repeated-value triple.
• Compare the quadratic approach with extending the hash-based two-sum strategy for each fixed first element.