Given an integer array nums of length n and an integer target, return the number of triplets of indices (i, j, k) satisfying $0 \leq i < j < k < n$ such that nums[i] $+$ nums[j] $+$ nums[k] $<$ target.

Constraints:

• n $==$ nums.length

• $0 \leq$ n $\leq 3500$

• $-100 \leq$ nums[i] $\leq 100$

• $-100 \leq$ target $\leq 100$

• The input is generated such that the answer is less than or equal to $10^9$.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.