Given an array of n integers and a target value target, find all unique triplets in the array that sum to target. The triplets must consist of distinct elements, and the result should not contain duplicate triplets.
分类: technical
难度: medium
标签:
答题技巧
Sorting the array first is crucial; after sorting, use the two-pointer technique to reduce time complexity; be careful with deduplication (skipping duplicate elements); handle edge cases (array length < 3, duplicate elements); expected time complexity O(n²), space O(1) or O(log n) depending on sorting.
参考答案
First sort the array. Then fix the first number nums[i] (i from 0 to n-3). Use two pointers left=i+1 and right=n-1 in the range [i+1, n-1] to find pairs that sum to target - nums[i]. When a valid triplet is found, add it to result. Skip duplicate elements when moving pointers. Can early terminate if nums[i] > 0 and target > 0 in some implementations.