c++ O(n^2) solution


  • 0
    Y
     int triangleNumber(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            
            int mx = nums.back();
            vector<int> mp(mx+1, -1);
            
            for(int i = 0; i < nums.size(); ++i){
                if(mp[nums[i]] == -1){
                    mp[nums[i]] = i;
                }
            }
            
            for(int i = mx-1; i >= 0; --i){
                if(mp[i] == -1){
                    mp[i] = mp[i+1];
                }
            }
            
            int cnt = 0;
            
            for(int i = 0; i < nums.size(); ++i){
                for(int j = i+1; j < nums.size(); ++j){
                    if(nums[i] + nums[j] > mx) cnt += max((int)nums.size() - 1 - j, 0);
                    else cnt += max(mp[nums[i] + nums[j]] - 1 - j, 0);
                }
            }
            
            return cnt;
        }
    

Log in to reply
 

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