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

在线评测地址：领扣题库官网

样例 1:

输入: [3, 4, 6, 7]
输出: 3
解释:
可以组成的是 (3, 4, 6), 
           (3, 6, 7),
           (4, 6, 7)
样例 2:
输入: [4, 4, 4, 4]
输出: 4
解释:
任何三个数都可以构成三角形
所以答案为 C(3, 4) = 4

题目理解

• 我们先考虑“三条边能构成三角形”的充分必要条件。我们首先想到的是“三角形的任意两边之和大于第三边，三角形的任意两边之差小于第三边”。如果从这个角度理解，代码编写比较麻烦，因为“任意”二字就要求我们去检验各种组合。
• 如果我们仔细分析一下这个条件，就不难证明它等效于“较短的两边之和大于最长边”。对于升序排列的三个数[a, b, c]，我们只需判断a + b > c是否成立，就知道它们是否能构成三角形。

解题思路

• 最直观的方法是暴力法，三重循环枚举，时间复杂度为O(n^3)。
• 如果先将数组排好序，二重循环固定较短两边a和b，然后再利用二分查找找到最大的满足a + b > c的c，这样可以将时间复杂度优化至O(n^2logn)
• 这里我们采用双指针方法，可以继续降低时间复杂度。首先固定最大边的位置 i，然后在 [0, i-1]之间利用双指针找到满足条件的三边。时间复杂度为O(n^2)。

算法流程

• 首先对数组进行升序排列。

• 从右向左遍历最大边，固定最大边的位置i

  • 建立双指针left和right，初始分别指向0和i-1
  • 如果S[left] + S[right] > S[i]，说明三者可以构成三角形。与此同时，最小边的索引为left+1, left+2,...,right-1时，都能与S[right]和S[i]构成三角形。所以满足条件的三角形找到了right-left个。然后right指针左移进入下一轮。
  • 如果S[left] + S[right] <= S[i]，说明不能构成三角形。left指针右移进入下一轮。

复杂度分析

• 时间复杂度为O(n^2)。外层遍历最大边是n，内层循环移动双指针是n，所以总复杂度为O(n^2)。
• 空间复杂度为O(1)，只需占用常量空间。

public class Solution {
    /**
     * @param S: A list of integers
     * @return: An integer
     */
    public int triangleCount(int[] S) {
        int res = 0;
        int left = 0, right = S.length - 1;
        // 先对S进行排序
        Arrays.sort(S);
        // 最大边从右向左遍历
        for (int i = 0; i < S.length; i++) {
            // 建立双指针
            left = 0;
            right = i - 1;
            while (left < right) {
                // 可以构成三角形
                if (S[left] + S[right] > S[i]) {
                    res += (right - left);
                    right --;
                }
                // 不能构成三角形
                else {
                    left ++;
                }
            }
        }
        return res;
    }
}

更多题解参考：九章官网solution