Mid/Senior
3Sum Smaller
Given an integer array nums and an integer target, return the number of index triplets (i, j, k) such that:
0 <= i < j < k < nums.lengthnums[i] + nums[j] + nums[k] < target
Your solution should be efficient enough for the given input size.
Example 1
Input
nums = [-2,0,1,3], target = 2Output
2The valid triplets are
[-2, 0, 1] and [-2, 0, 3], both of which have sums less than 2.Example 2
Input
nums = [0], target = 0Output
0There are fewer than three numbers, so no triplet can be formed.
Constraints
- 0 <= nums.length <= 3500
- -100 <= nums[i] <= 100
- -100 <= target <= 100
Asked at 7 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.