Does a Triplet Add Up to the Target?
You are given an integer array nums and an integer target.
Return true if there are three different positions i, j and l such that nums[i] + nums[j] + nums[l] == target. Otherwise return false.
Note
The three positions must be different. The same value may be used more than once only if it appears at more than one position. If nums has fewer than three elements, the answer is false.
Trying every triplet takes O(n³). Sort the array first. Then fix the first element and look for the other two with two pointers, one at each end of the rest. This takes O(n²).
Examples
Example 1
- Input:
- [8,-3,5,1,10], 12
- Output:
- true
-3 + 5 + 10 = 12, using three different positions.
Example 2
- Input:
- [4,4,1], 12
- Output:
- false
The only triplet is 4 + 4 + 1 = 9. Using 4 three times is not allowed, because 4 appears at only two positions.
Example 3
- Input:
- [2,7], 9
- Output:
- false
There are fewer than three elements, so no triplet exists.
Constraints
0 <= nums.length <= 15-20 <= nums[i] <= 20-60 <= target <= 60
Run checks your code against the 3 examples. Submit checks it against all 303 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.