259. 3Sum Smaller ------------M

Given an array of n integers nums and an integer 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.

Follow up: Could you solve it in O(n2) runtime?

 

Example 1:

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]

Example 2:

Input: nums = [], target = 0
Output: 0

Example 3:

Input: nums = [0], target = 0
Output: 0

 

Constraints:

• n == nums.length
• 0 <= n <= 300
• -100 <= nums[i] <= 100
• -100 <= target <= 100

A:
思路很直观，就是 two pointer techniques
内层要计算的时候， 每次考虑的是： 前一个固定，一共有多少个合适的。

class Solution {
public:
    int threeSumSmaller(vector<int>& nums, int target) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int res = 0;
        for(int i =0;i<n-2;i++){
            int k = n-1; // increase k would get smaller
            for(int j = i+1;j<k;j++ ){
                while(k > j && nums[i] + nums[j] + nums[k] >= target){ //k is strictly decreasing
                    k--;
                }
                res += k-j;
            }
        }
        return res;
    }
};

Mistakes: