3Sum Smaller

Given an array of integers and a target value, find the number of unique triplets in the array whose sum is strictly less than the target value. This is a common problem that tests your ability to efficiently search and count combinations within a dataset.

Problem Description

You are given an array of integers nums and an integer target. Your task is to find the number of distinct triplets (i, j, k) such that i < j < k and nums[i] + nums[j] + nums[k] < target.

Key Requirements:

• Identify all unique combinations of three elements from the array.
• Calculate the sum of each triplet.
• Count only those triplets whose sum is strictly less than the given target.
• The indices i, j, and k must be distinct and in increasing order (i < j < k).

Expected Behavior:

The function should return a single integer representing the count of such triplets.

Edge Cases:

• An empty input array.
• An array with fewer than three elements.
• A target value that is very small, making it impossible to form any triplets less than the target.
• A target value that is very large, potentially including all possible triplets.

Examples

Example 1:

Input: nums = [-2, 0, 1, 3], target = 2
Output: 2
Explanation: The two triplets whose sum is less than 2 are:
[-2, 0, 1] (sum: -1)
[-2, 0, 3] (sum: 1)

Example 2:

Input: nums = [], target = 0
Output: 0
Explanation: The input array is empty, so no triplets can be formed.

Example 3:

Input: nums = [1, 1, -2], target = 1
Output: 1
Explanation: The triplet is [-2, 1, 1] (sum: 0).

Constraints

• 0 <= nums.length <= 3500
• -100 <= nums[i] <= 100
• -100 <= target <= 100
• The time complexity of your solution should be better than O(n^3).

Notes

• Sorting the input array can be a helpful first step. Consider how sorting might simplify the process of finding triplets.
• Think about how you can efficiently avoid redundant calculations and checks.
• The problem asks for the count of triplets, not the triplets themselves.