259. 3Sum Smaller (Medium)

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.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. 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 1: Brute Force

Time Complexity: $$O(n^3)$$

这道题是3Sum问题的一个变形，让我们求三数之和小于一个目标值，那么最简单的方法就是穷举法，将所有的可能的三个数字的组合都遍历一遍，比较三数之和跟目标值之间的大小，小于的话则结果自增1，参见代码如下:

int threeSumSmaller(vector<int>& nums, int target) {
    int res = 0, n = nums.size();
    sort(nums.begin(), nums.end());
    for (int i = 0; i < n; ++i) {
        int sum = target-nums[i];
        for (int j = i+1; j < n; ++j) {
            int target2 = sum - nums[j];
            for (int k = j+1; k < n; ++k) {
                if (nums[k] < target2) ++res;
            }
        }
    }
    return res;
}

Solution 2: Two Pointers

Time Complexity: $$O(n^2)$$

这里面有个trick就是当判断三个数之和小于目标值时，此时结果应该加上j-i，因为数组排序了以后，如果加上num[j]小于目标值的话，那么加上一个更小的数必定也会小于目标值，然后我们将左指针右移一位，否则我们将右指针左移一位

After sorting, if i, j, k is a valid triple, then i, j-1, k, ..., i, i+1, k are also valid triples. No need to count them one by one.

int threeSumSmaller(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int cnt = 0;
    for (int k = 2; k < nums.size(); k++) {
        int i = 0, j = k-1, t = target-nums[k];
        while (i < j) {
            if (nums[i]+nums[j] < t) {
                cnt += j-i;
                ++i;
            } else --j;
        }
    }
    return cnt;
}