3Sum Smaller
Medium
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
.
Example:
Follow up: Could you solve it i nO(n^2) runtime?
Solution & Analysis
Two Pointers - Time O(n^2), Space O(1) - (4 ms, faster than 56.85%)
基本思想跟3Sum一样,不同之处在于nums[i] + nums[j] + nums[k] < target
的时候,记录count += k - j
,因为k在当前位置就满足smaller条件,那么一直到j + 1都可以满足,所以直接加上中间所有的可能组合;之后只移动j
指针。
Last updated