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?

Have you met this question in a real interview?

Yes

Example

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

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

Given array S =[4,4,4,4], return4. 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)]

思路

首先判断三条边能否组成三角形的条件是，较小的两边之和是否大于第三边。

第二，我们要排除重复计算的情况。

暴力解法就是枚举三条边下标，排除重复后O(n^3)的时间复杂度。

这题可以根据三角形的判断定律，用两个指针把这个变成一个two sum less than 的变型。我们可以枚举最长的一条边。然后在剩下的数组内寻找有多少个两个元素相加大于这条最长边的组合。

1. 排序
2. 从右侧开始枚举，并且左指针从头，右指针从枚举的位置向左移动一位

public class Solution {
    /*
     * @param S: A list of integers
     * @return: An integer
     */
    public int triangleCount(int[] S) {
        // write your code here
        if (S == null || S.length < 3) {
            return 0;
        }

        int count = 0;
        Arrays.sort(S);
        for (int i = S.length - 1; i > 1; i--) {
            count += twoSum(i, S);
        }
        return count;
    }

    private int twoSum(int longVerticeIndex, int[] S) {
        int i = 0;
        int j = longVerticeIndex - 1;
        int count = 0;


        while (i < j) {
            if (S[i] + S[j] <= S[longVerticeIndex]) {
                i++;
            } else {
                count += j - i;
                j--;
            }
        }
        return count;
    }


}