Java O(n^2) solution, similar to 3 sum problem


  • 1

    We only need to satisfy the condition that the sum of the two shorter edges is strictly greater than the longest edge.

        public int triangleNumber(int[] nums) {
            int n = nums.length;
            if (n < 3) return 0;
            Arrays.sort(nums);
            int ans = 0;
            for (int i = 0; i < nums.length-2; i++) {
                for (int j = i+1, k = i+2; k < nums.length; k++) {
                    while (j < k && nums[i]+nums[j] <= nums[k]) j++;
                    ans += k-j;
                }
            }
            return ans;
        }
    

Log in to reply
 

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