259 3Sum Smaller
Last updated
Was this helpful?
Last updated
Was this helpful?
Given an array ofnintegersnumsand atarget, find the number of index tripletsi, j, k
with0 <= i < j < k < n
that satisfy the conditionnums[i] + nums[j] + nums[k] < target
.
For example, givennums=[-2, 0, 1, 3]
, andtarget= 2.
Return 2. Because there are two triplets which sums are less than 2:
Follow up: Could you solve it inO(n^2) runtime?
(1) Two Pointers
时间复杂度O(n^2), 空间复杂度O(1)