Binary search solution and 3-pointer solution


  • 0
    E

    Solution 1:binary search
    For a,b,c,if abs(b-c)<a<b+c, a b c can create a triangle.
    So binary search abs(b-c) and b+c.

    int triangleNumber(vector<int>& nums) {
        if(nums.size()<3)return 0;
        sort(nums.begin(),nums.end());
        int c=0;
        for(int i=0;i<nums.size()-2;i++){
            if(nums[i]==0)continue;
            for(int j=i+1;j<nums.size()-1;j++){
                int a=abs(nums[i]-nums[j]),b=nums[i]+nums[j];
                int ap=upper_bound(nums.begin()+j+1,nums.end(),a)-nums.begin(),bp=lower_bound(nums.begin()+j+1,nums.end(),b)-nums.begin();
                c+=bp-ap;
            }
        }
        return c;
    }
    

    Solution 2:3-pointer(better than solution 1)
    If a<b<c and a+b>c, a b c can create a triangle

    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int c=0;
        for(int i=nums.size()-1;i>=2;i--){
            int l=0,r=i-1;
            while(l<r){
                if(nums[l]+nums[r]>nums[i]){c+=r-l;r--;}
                else l++;
            }
        }
        return c;
    }
    

Log in to reply
 

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