Triangle Count

Question

Given an array of integers, how many three numbers can be found in the array, so that we can build an triangle whose three edges length is the three numbers that we find?

Example

Given array S = [3,4,6,7], return 3. They are:

[3,4,6]
[3,6,7]
[4,6,7]

Given array S = [4,4,4,4], return 4. They are:

[4(1),4(2),4(3)]
[4(1),4(2),4(4)]
[4(1),4(3),4(4)]
[4(2),4(3),4(4)]

Thoughts

三个长度能形成三条边的条件，任意两条边的和大于第三条，任意两条边的差小于第三条

我们可以先将array sort一下，然后i,j,k,分别i s[k], 差的条件必然能满足

brute force

3个for loop, O(n^3)

二分法

对前两条边for loop, 第三条边可根据条件进行二分查找

two pointer,

对于第一个i loop-through， 另外两条边可对于剩下的长度进行2 pointer计算，p1和p2

注意： 当p1前进到下一个时，p2可以不用reset为p1+1, 因为已经sort过了，所以s[p1+1] + s[i] > s[p1] + s[i] < s[p2], 可以直接往下找下一个结果跳过重复计算

1point3acres triangle count

Solution

class Solution:
    # @param S: a list of integers
    # @return: a integer
    def triangleCount(self, S):
        # write your code here
        if not S or len(S) < 3:
            return 0
        S.sort()
        result = 0

        for i in range(len(S)-2):
            p1 = i + 1
            p2 = p1 + 1
            while p1 < len(S):
                while p2 < len(S) and S[p2] < S[i] + S[p1]:
                    p2 += 1
                result += p2 - p1 - 1
                p1 += 1
        return result