259. 3Sum Smaller

Description

Given an array of n integers nums and a target, find the number of index trip letsi, j, kwith0 <= i < j < k < nthat satisfy the conditionnums[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(n2) runtime?

Note

Think about what would be changed after the nums array is sorted.

Code

class Solution {
public:
    int threeSumSmaller(vector<int>& nums, int target) {
        if(0 == nums.size()) 
            return 0;

        sort(nums.begin(), nums.end());
        int rst = 0;
        for(int loop = 0; loop < nums.size() - 2; ++loop) {
            if(nums[loop] + nums[loop + 1] + nums[loop + 2] >= target)
                break;
            for(int second = loop + 1; second < nums.size() - 1; ++second) {
                int third = nums.size() - 1;
                while(second < third && nums[loop] + nums[second] + nums[third] >= target) --third;
                rst += third - second;
            }
        }       
        return rst;
    }
};