题目：
Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle. Example 1:
Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are:
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3
Note:
The length of the given array won't exceed 1000.
The integers in the given array are in the range of [0, 1000].
解析：
首先如何判断三个边长能否组成一个三角形，这个初中数学就学过——两个小边的和大于最大边的边长。
def checkValid(self,a,b,c):
return (a+b) > c
因此，很容易得到解法，对nums数组排序后，做全排列，依次检查每种组合是否符合要求。
def triangleNumber2(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
count = 0
nums.sort()
for i in range(0,len(nums)-2):
for j in range(i+1,len(nums)-1):
for k in range(j+1,len(nums)):
if True == self.checkValid(nums[i], nums[j], nums[k]):
count += 1
#print nums[i], nums[j], nums[k]
else:
break
return count
但是非常遗憾，这种解法的复杂度是 O(n*3)，超时了。根据判定中给出的超时输入发现，nums里面很多边长的数值是相同的。
Last executed input:
[33,97,81,65,30,58,83,83,66,85,78,40,51,61,86,94,42,17,35,18,45,27,56,78,36,97,6,51,76,26,68,68,61,87,13,98,93,80,24,34,19,90,85,89,83,15,41,52,25,16,61,51,19,6,40,79,25,88,65,85,0,42,78,27,30,68,47,67,40,26,15,72,20,45,88,82,12,82,95,1,46,56,83,20,65,39,13,92,36,99,74,50,46,8,27,45,36,55,50,0]
因此可以考虑优化算法，首先统计三个边长都不一样的情况，然后再考虑等腰三角形的情况，最后是等边三角形。
def triangleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
#用一个list计数所有边长出线的次数，下标是边长值，对应的值是边长值出现的次数
count = 0
l = []
for i in range(0,1000+1):
l.append(0) for i in nums:
l[i] += 1
for i in range(1,len(l)-2):
if l[i] == 0:
continue
for j in range(i+1,len(l)-1):
if l[j] == 0:
continue
for k in range(j+1,len(l)):
if l[k] == 0:
continue
if True == self.checkValid(i,j,k):
count += (l[i]*l[j]*l[k])
else:
break
#dup
for i in range(1,len(l)):
if l[i] == 0 or l[i] == 1:
continue
else:
#print 'i:',i
#等腰三角形，如果某个边长值的出线的次数为n（n>=2），表示可以组成等腰三角形。根据组合的原理，两个腰可以得到C(2,n)
#然后根据 2*边长值与其他非自身边长值进行比较，得到等腰三角形的数量
for j in range(1,len(l)):
if 2*i > j and l[j] > 0 and j != i:
count += (l[i]*(l[i]-1))/2*l[j]
#等边三角形，这个也是组合，如果某个边长值的出线的次数为n（n>=3），表示可以组成等边三角形。
#根据组合的原理，可以等到的种数为C(3,n)
if l[i] >= 3:
count += (l[i]*(l[i]-1)*(l[i]-2))/6 return count
这样优化之后，效率得到了很大的提升，但是还是不够。进一步检查发现，list中无效的元素太多，可以考虑过滤掉很多边长值出现次数为0的元素，如代码所示，用一个ul对l中的数据进行过滤。
def triangleNumber3(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
count = 0
l = []
for i in range(0,1000+1):
l.append(0) for i in nums:
l[i] += 1
#print l
ul = []
for i in range(0,len(l)):
if l[i] > 0:
ul.append(i)
#print ul
for i in range(0,len(ul)-2):
for j in range(i+1,len(ul)-1):
for k in range(j+1,len(ul)):
if True == self.checkValid(ul[i],ul[j],ul[k]):
count += (l[ul[i]]*l[ul[j]]*l[ul[k]])
#print i,j,k
else:
break
#dup
#print count
for i in range(0,len(ul)):
if l[ul[i]] == 0 or l[ul[i]] == 1 or ul[i] == 0:
continue
else:
#print 'i:',i
for j in range(0,len(ul)):
if 2*ul[i] > ul[j] and l[ul[j]] > 0 and j != i and ul[j] != 0:
#print (l[i]*(l[i]-1))/2
count += (l[ul[i]]*(l[ul[i]]-1))/2*l[ul[j]]
#print count
if l[ul[i]] >= 3:
count += (l[ul[i]]*(l[ul[i]]-1)*(l[ul[i]]-2))/6 return count
这样再一优化之后，终于通过了。