LintCode 382 [Triangle Count]

原题

给定一个整数数组，在该数组中，寻找三个数，分别代表三角形三条边的长度，问，可以寻找到多少组这样的三个数来组成三角形？

样例
例如，给定数组 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