# Solution Similar to Leetcode 259. 3Sum Smaller

• /** 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;
}
``````

• 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

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

• 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
``````

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