12ms cpp solution


  • 0
    T
    int triangleNumber(vector<int>& nums) {
        int n=nums.size();
        int res=0;
        if(n==0)return res;
        sort(nums.begin(),nums.end());
        int sp[1005];
        memset(sp,-1,sizeof(sp));
        sp[nums[0]]=0;
        for(int i=1;i<n;i++){
            if(nums[i]!=nums[i-1])sp[nums[i]]=i;
        }
        for(int i=1000;i>=1;i--){
            if(sp[i]==-1)sp[i]=sp[i+1];
        }
        for(int i=0;i<n;i++){
            if(nums[i]==0)continue;
            for(int j=i+1;j<n;j++){
                int d=nums[j]-nums[i];
                int add;
                if(i>=sp[d+1])add=(j-i-1);
                else add=j-sp[d+1];
                res+=add;
            }
        }
        return res;
    }
    

Log in to reply
 

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