Count Pairs Whose Sum is Less than Target
Given a 0-indexed integer array nums of length n and an integer target, return the number of pairs (i, j) where 0 <= i < j < n and nums[i] + nums[j] < target.
Example 1
Input
nums = [-1,1,2,3,1], target = 2Output
3There are 3 valid pairs:
(0, 1), (0, 2), and (0, 4), while (0, 3) is not counted because its sum is not strictly less than target.Example 2
Input
nums = [-6,2,5,-2,-7,-1,3], target = -2Output
10There are 10 pairs of indices whose values sum to less than
target.Constraints
- 1 <= nums.length == n <= 50
- -50 <= nums[i], target <= 50