# Java 22ms O(n^2) Time O(1) Space with explanation

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

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