原题
给定一个整数数组，在该数组中，寻找三个数，分别代表三角形三条边的长度，问，可以寻找到多少组这样的三个数来组成三角形？
样例
例如，给定数组 S = {3,4,6,7}，返回 3
其中我们可以找到的三个三角形为：
{3,4,6}
{3,6,7}
{4,6,7}
给定数组 S = {4,4,4,4}, 返回 4
其中我们可以找到的四个三角形为：
{4(1),4(2),4(3)}
{4(1),4(2),4(4)}
{4(1),4(3),4(4)}
{4(2),4(3),4(4)}
解题思路
- 最原始解法：三层for循环，下面的每层循环终止条件是为了防止重复扫描，因为
i = 1, j = 2, k = 3与i = 3, j = 2, k = 1等这些都其实是一样的。最后时间复杂度为O(n^3)
for i = 0 ~ n
for j = 0 ~ i
for k = 0 ~ j
- 更优解 - Two Pointers，可以将本题转化为Two Sum II问题。
- 因为k < i < j，所以在判断是否能组成三角形的时候，有两个判断可以省略
- S[i] + S[j] > S[k] (可省略)
- S[i] + S[k] > S[j] (可省略)
- S[j] + S[k] > S[i]
- 最终,即for i = 0 ~ n，求在0 ~ i中有多少S[j] + S[k] > target(即S[i])。时间复杂度从O(n^3) -> O(n^2)
完整代码
class Solution:
# @param S: a list of integers
# @return: a integer
def triangleCount(self, S):
# write your code hereedges = sorted(S, reverse=True)
count = 0
if not S or len(S) < 3:
return count
S.sort()
for i in range(2, len(S)):
longest = S[i]
left = 0
right = i - 1
while left < right:
if S[left] + S[right] <= longest:
left += 1
elif S[left] + S[right] > longest:
count += right - left
right -= 1
return count
