Java O(n^2 logn) solution using binary search


  • 0
    K
    public class Solution {
        public int triangleNumber(int[] nums) {
            Arrays.sort(nums);
            int ans = 0;
            for(int i = 0; i < nums.length; ++i) {
                for(int j = i+1; j < nums.length; ++j) {
                    ans += binarySearch(nums, nums[i], nums[j], j) - j;
                }
            }
            return ans;
        }
        
        private int binarySearch(int[] nums, int a, int b, int start) {
            int lo = start, hi = nums.length;
            while(hi-lo>1) {
                int mid = (lo+hi)/2;
                if(check(a, b, nums[mid])) {
                    lo = mid;
                }
                else
                {
                    hi = mid;
                }
            }
            return lo;
        }
        
        private boolean check(int a, int b, int c) {
            return a+b>c && a+c>b && b+c>a;
        }
    }
    

Log in to reply
 

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