◻️918. 3Sum Smaller (medium)

[Lintcode] Problem Link: https://www.lintcode.com/problem/924/description

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

Example1

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

Example2

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

---

Solutions

Optimised

Runtime 20 ms Memory 2.44 MB

```cpp
class Solution {
public:
    /**
     * @param nums:  an array of n integers
     * @param target: a target
     * @return: the number of index triplets satisfy the condition nums[i] + nums[j] + nums[k] < target
     */
    int threeSumSmaller(vector<int> &nums, int target) {
        int n = nums.size();
        if (n < 3) return 0;

        sort(nums.begin(), nums.end());
        int cnt=0;
        for (int i=0; i+2 < n; ++i) {
            int l=i+1, r=n-1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum < target) {
                    cnt = cnt + (r-l); // Because if i+l+r is less than target -> then r,(r-1),(r-2),...,l will also be less than target
                    ++l;
                } else {
                    --r;
                }
            }
        }
        return cnt;
    }
};
```