Practice/Stripe/Leetcode 15. 3Sum

Leetcode 15. 3Sum

CodingMust

Problem

Given an integer array and a target sum, find all unique triplets in the array where the sum of the three elements equals the target. Each triplet should be returned in ascending order, and the result set must not contain duplicate triplets.

Your task is to implement an efficient algorithm that avoids generating duplicate triplets while exploring all possible combinations of three numbers.

Requirements

1. Return all unique triplets that sum to the target value
2. Each triplet should be sorted in ascending order
3. The result list should not contain duplicate triplets
4. Handle arrays with duplicate numbers correctly
5. Return an empty list if no valid triplets exist

Constraints

• 3 ≤ nums.length ≤ 3000
• -105 ≤ nums[i] ≤ 105
• -105 ≤ target ≤ 105
• Time complexity should be better than O(n3)

Examples

Example 1:

Input: nums = [-1, 0, 1, 2, -1, -4], target = 0 Output: [[-1, -1, 2], [-1, 0, 1]] Explanation: The two unique triplets that sum to 0 are: -1 + (-1) + 2 = 0 -1 + 0 + 1 = 0

Example 2:

Input: nums = [1, 2, 3], target = 0 Output: [] Explanation: No three positive numbers can sum to zero.

Example 3:

Input: nums = [0, 0, 0, 0], target = 0 Output: [[0, 0, 0]] Explanation: The only unique triplet is three zeros.

Example 4:

Input: nums = [-2, 0, 1, 1, 2], target = 0 Output: [[-2, 0, 2], [-2, 1, 1]] Explanation: Both triplets are unique and sum to the target.