```
import heapq
class Solution(object):
def triangleNumber(self, nums):
nums = sorted(nums)
ans = 0
pre = []
c = 0
m = None
for i in range(len(nums)-2):
for j in range(i,-1,-1):
t = nums[i+1] + nums[j]
if t> nums[i+2]:
c += 1
heapq.heappush(pre,t)
if not m or t<m:
m = t
else:
break
flag = 0
while m and pre and m <= nums[i+2]:
m = heapq.heappop(pre)
c -= 1
flag = 1
if flag and m>nums[i+2]:
heapq.heappush(pre,m)
c+=1
ans += c
return ans
```

I thought this one is better than O(n^2), but apparently not