C++ code use lower_bound to do binary search


  • 0
    A
    class Solution {
    public:
        int triangleNumber(vector<int>& nums) {
            int i, j;
            int Result = 0;
    		
            sort(nums.begin(), nums.end());
    		
            for(i = 0; i < nums.size(); i++)
            {
                for(j = i + 1; j < nums.size() - 1; j++)
                {
                    // Get valid triangles count
                    Result += lower_bound(nums.begin() + j + 1, nums.end(), (nums[i] + nums[j])) - nums.begin() - j - 1;
                }
            }
    		
            return Result;
        }
    };
    

Log in to reply
 

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