Solution Similar to Leetcode 259. 3Sum Smaller


  • 2
    X

    /** we need to find 3 number, i < j < k, and a[i] + a[j] > a[k];
    * if we sort the array, then we can easily use two pointer to find all the pairs we need.
    * if at some point a[left] + a[right] > a[i], all the elements from left to right-1 are valid.
    * because they are all greater then a[left];
    * so we do count += right - left; and right--
    *
    * otherwise, we increment left till we get a valid pair.

    public int triangleNumber(int[] nums) {
    		if (nums == null || nums.length <= 2) {
    			return 0;
    		}
    		Arrays.sort(nums);
    		int count = 0;
    		
    		for (int i = 0; i < nums.length; i++) {
    			int left = 0, right = i-1;
    			while (left < right) {
    				if (nums[left] + nums[right] > nums[i]) {
    					count += right - left;
    					right--;
    				} else {
    					left++;
    				}
    			}
    		}
    		
    		return count;
        }
    

  • 1
    A

    good one. like it.
    BTW, the triangle numbers are the numbers that need to meet these conditions:
    a+b>c && a+c>b && c+b>a
    after soring the array, if a<b<c, it only need to find (a,b) pairs their sum is greater than c


  • 1

    @xmztzt This is not O(nlog(n)). This is O(n^2).


  • 0
    A

  • 0
    X

    @compton_scatter that's true. my bad, forget about the while loop.


  • 0

    Thanks for the solution! This is Python version.

    def triangleNumber(self, nums):
        n, res = len(nums), 0
        if n < 3:
            return 0
        nums.sort()
        for i in range(2, n):
            left, right = 0, i-1
            while left < right:
                if nums[left] + nums[right] > nums[i]:
                    res += right - left
                    right -= 1
                else:
                    left += 1
        return res
    
    # 243 / 243 test cases passed. Runtime: 1755 ms
    

Log in to reply
 

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