Given a list of integers nums and an integer target, return the number of index triples (i, j, k) with i < j < k such that nums[i] + nums[j] + nums[k] < target.
Examples
Input: nums = [-2, 0, 1, 3], target = 2
Output: 2
Explanation: [-2, 0, 1] and [-2, 0, 3] have sums below 2.
Input: nums = [3, 5, 7], target = 10
Output: 0
Constraints
0 <= len(nums) <= 3000,-10**4 <= nums[i] <= 10**4- Target: O(n^2) time after sorting, O(1) extra space.
Goals
- Count a whole block of valid triples in O(1) when the inner sum is small enough
- Combine an outer loop with an inner converging scan