LeetCode "3Sum Smaller"

A variation of 3Sum. And the trick is, (i<j<k) restriction doesn't mean anything here!

class Solution {
public:
    int threeSumSmaller(vector<int>& nums, int target) 
    {
        size_t len = nums.size();
        if(len < 3) return 0;
        
        sort(nums.begin(), nums.end());
        
        int ret = 0, i = 0, j = 1, k = len - 1;
        for(int i = 0; i < len - 2; i ++)
        {
            j = i + 1; k = len - 1;
            while(j < k)
            {
                int curr = nums[i] + nums[j] + nums[k];
                if (curr >= target) 
                    k--;
                else
                {
                    ret += k - j;
                    j ++;
                }
            }
        }
            
        return ret;
    }
};
View Code
原文地址:https://www.cnblogs.com/tonix/p/4754702.html