• Time:O(n^2)
• Space:O(1)

C++

``````class Solution {
public:
int triangleNumber(vector<int>& nums) {
if (nums.size() < 3)
return 0;

int ans = 0;

sort(begin(nums), end(nums));

for (int k = nums.size() - 1; k > 1; --k) {
int i = 0;
int j = k - 1;
while (i < j)
if (nums[i] + nums[j] > nums[k]) {
// (nums[i], nums[j], nums[k])
// (nums[i + 1], nums[j], nums[k])
// ...
// (nums[j - 1], nums[j], nums[k])
ans += j - i;
--j;
} else {
++i;
}
}

return ans;
}
};
``````

JAVA

``````class Solution {
public int triangleNumber(int[] nums) {
if (nums.length < 3)
return 0;

int ans = 0;

Arrays.sort(nums);

for (int k = nums.length - 1; k > 1; --k) {
int i = 0;
int j = k - 1;
while (i < j)
if (nums[i] + nums[j] > nums[k]) {
// (nums[i], nums[j], nums[k])
// (nums[i + 1], nums[j], nums[k])
// ...
// (nums[j - 1], nums[j], nums[k])
ans += j - i;
--j;
} else {
++i;
}
}

return ans;
}
}
``````

Python

``````class Solution:
def triangleNumber(self, nums: List[int]) -> int:
ans = 0

nums.sort()

for k in range(len(nums) - 1, 1, -1):
i = 0
j = k - 1
while i < j:
if nums[i] + nums[j] > nums[k]:
ans += j - i
j -= 1
else:
i += 1

return ans
``````