# Question

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

Example:

Input: nums = [-2,0,1,3], and target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]


Follow up: Could you solve it in $$O(n^2)$$ runtime?

# Solution

Key observation: the answer does not change if numbers are swapped. Thus we can sort the numbers first and use a sliding window method.

We count the number of such combinations for each $$i$$, so that we can reduce the problem to 2Sum smaller. For 2Sum Smaller, we initialize two indices, left and right, pointing to the first and last element respectively. If nums[left] + nums[right] >= target - nums[i], then there are no combinations with i and k = right (because j = left is the smallest), and we need to reduce right. Else, there are right - left pair of (j, k) when j = left, and we can add them to the number of combinations and increment left.

class Solution(object):
def threeSumSmaller(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if len(nums) < 3:
return 0

sums = 0
nums.sort()
for i in range(len(nums) - 2):
sums += self.__twoSumSmaller(nums[i+1:], target - nums[i])

return sums

def __twoSumSmaller(self, nums, target):
sums = 0
left, right = 0, len(nums) - 1
while left < right:
if nums[left] + nums[right] < target:
sums += right - left
left += 1
else:
right -= 1

return sums