题目：给定一个整数数组，在该数组中，寻找三个数，分别代表三角形三条边的长度，问，可以寻找到多少组这样的三个数来组成三角形？样例 例如，给定数组 S = {3,4,6,7}，返回 3其中我们可以找到的三个三角形为： {3,4,6} {3,6,7} {4,6,7} 给定数组 S = {4,4,4,4}, 返回 4第一次思路：直接遍历数组，找出三个数，然后判断是否满足三角形条件满足三角形的条件有两种:①任取两条相加大于第三条和两条相减小于第三条；②两两相加都大于第三边由于是要在数组上面找三条，也就是第一条不可能出现在倒数第二条，及（0,1,2,3，…，n-2,n-1)第一次循环范围0–n-3,但是注意到range的使用是不包括右边，则i in range(0,n-2),则第二条j in range（i+1,n-1),第三条 z in range(j+1,n). 代码如下：def triangleCount(self, S):
# write your code here
if len(S)<3:
return;
count=0;
len1=len(S)
for i in range(0,len1-2):
for j in range(i+1,len(S)-1):
for z in range(j+1,len(S)):
if tri(S[i],S[j],S[z])==1:
print(S[i],S[j],S[z])
count+=1
return count
def tri(a,b,c):
if a+b>c and a+c>b and b+c>a:
return 1
else:
return 0
然而因为三次循环，所以导致Time Limit Exceeded。 缩短为两次循环，思路如下：将输入的数组（列表）通过list.sort()进行从小到大的排序。采用二分法：每次找到最大值和最小值，然后得到他们的差，取他们的中间值判断与差的大小，来判断中间值在哪个位置，则该位置到最大值的位置的值都是符合要求的值，将该范围的数量为满足条件的count两次循环，找到所有的count+=count.return count代码如下：def triangleCount(self, S):
# write your code here
if len(S)<3:
return;
count=0;
S.sort();#从小到大排序
for i in range(0,len(S)):
for j in range(i+1,len(S)):
w,r=i+1,j
target=S[j]-S[i]
while w<r:
mid=(w +r)//2
#取整数
S_mid=S[mid]
if S_mid>target:
r=mid
else:
w=mid+1
count+=(j-w)
return count
总结：本题思路比较清晰，要尽量少使用迭代或者遍历的算法，很容易出现时间和内存的限制。}