232. 3Sum Smaller
You are given an array of integers nums and an integer target. Count how many index triples (i, j, k) with 0 <= i < j < k < nums.length satisfy
nums[i] + nums[j] + nums[k] < target
and return that count. Note that you only need how many such triples exist, not the triples themselves — that difference is exactly what unlocks a solution faster than checking every triple.
If the array holds fewer than three elements, the answer is 0.
Example 1:
Input: nums = [3, 1, -2, 5, 0], target = 4
Output: 4
Explanation: Four value combinations stay under 4: (-2, 0, 1), (-2, 0, 3), (-2, 0, 5) and (-2, 1, 3). Every other triple sums to 4 or more.
Example 2:
Input: nums = [0, 0, 0], target = 1
Output: 1
Explanation: The only possible triple sums to 0, which is less than 1.
Constraints:
- 0 ≤ nums.length ≤ 3000
- -100 ≤ nums[i] ≤ 100
- -100 ≤ target ≤ 100
- The count can exceed a 32-bit integer at the largest sizes — use a 64-bit counter.
Hints:
The condition i < j < k just says "pick three distinct positions" — the count does not depend on the order of the array. That means you are free to sort first.
After sorting, fix the smallest element at index i and put two pointers at i+1 and the end. If nums[i] + nums[lo] + nums[hi] < target, then replacing hi with ANY index between lo and hi also works — that is hi − lo triples counted in one step. Then move lo up; otherwise move hi down.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [3, 1, -2, 5, 0], target = 4
Expected output: 4