- In this situation, if the smallest value + the middle one > the largest one ,then it's a triangle, (because a triangle requires the sum of each two sides must be greater than the other one, s+m is the smallest sum in the three sums, if this > the largest side, it'll surely be a triangle), so this problem is equal to three sum problem (find the combinations which sum is larger than a given number)
- The main idea is to sort the array first(with O(nlogn) time complexity) to decrease the time complexity and go trough the array with two loops in O(n^2) ,so the final is O(n^2), otherwise three loops is O(n^3) which is more than this.

```
public class Solution {
public int triangleNumber(int[] nums) {
if (nums.length < 3) {
return 0;
}
int count = 0;
Arrays.sort(nums); // O(nlogn) time
for (int k = nums.length - 1; k > 1; k--) { // O(n)
int begin = 0;
int end = k - 1;
while (begin < end) { // O(n), O(n^2) in total
if (isTriangle(nums[begin], nums[end], nums[k])) {
// if 'begin' match, then all the nums from begin to end match, so there is no need to go through all the numbers
count += (to - from);
to--;
}
else {
from++;
}
}
}
return count;
}
public boolean isTriangle(int a, int b, int c) {
return (a + b) > c && (a + c) > b && (b + c) > a;
}
}
```