C++ solution beats 100%!


  • 0
    M
        int triangleNumber(vector<int>& nums) {
            if(nums.size()<3) return 0;
            int res=0;
            sort(nums.begin(), nums.end());
            for(int i=0;i<nums.size()-2;i++) {
                int s=i+1, e=i+2;
                while(e!=nums.size()) {
                    while(nums[i]+nums[s]>nums[e]&&e<nums.size()) e++;
                    if(e>=nums.size()) break;
                    res+=e-1-s;
                    s++;
                    if(e<=s) e=s+1;
                }
                res+=(nums.size()-s)*(nums.size()-1-s)/2;
            }
            return res;
        }

Log in to reply
 

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