My O(n^2) c++ solution


  • 3
    M
    class Solution {
    public:
        int threeSumSmaller(vector<int>& nums, int target) {
            sort(nums.begin(),nums.end());
            if(nums.size()<3)
            return 0;
            int start = 0, end = nums.size()-1;
            int count = 0;
            while(start<end){
                int a = nums[start];
                int left = start+1, right = end;
                while(left<right){
                    int b = nums[left], c = nums[right];
                    if(a+b+c >= target){
                        right--;
                    }
                    else if(a+b+c < target){
                        count = count + right - left;
                        left++;
                    }
                }
                start++;
            }
            return count;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.