Simple c++, Beats 95%


  • 0
    H
    class Solution {
    public:
        int twoSumSmaller(vector<int>& nums, int p, int target) {
            int n = nums.size();
            int i=0, j=n-1;
            int count=0;
            while(i<p && p<j) {
                int sum=nums[i]+nums[j];
                if(sum>=target) {j--; continue;}
                if(sum<target) {count+=j-p; i++; continue;}
            }
            return count;
        }
        int threeSumSmaller(vector<int>& nums, int target) {
            sort(nums.begin(), nums.end());
            int sum=0, n=nums.size();
            for(int i=1; i<n-1; i++) {
                sum += twoSumSmaller(nums, i, target-nums[i]);
            }
            return sum;
        }
    };

Log in to reply
 

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