611. Valid Triangle Number

Given an integer array nums, return the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

Input: nums = [2,2,3,4]
Output: 3
Explanation: Valid combinations are: 
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Example 2:

Input: nums = [4,2,3,4]
Output: 4

Constraints:

• 1 <= nums.length <= 1000

• 0 <= nums[i] <= 1000

Solution:

https://www.jiuzhang.com/problem/triangle-count/ Version 1:

• 最直观的方法是暴力法，三重循环枚举，时间复杂度为O(n3)O(n3)。

• 如果先将数组排好序，二重循环固定较短两边a和b，然后再利用二分查找找到最大的满足a + b > c的c，这样可以将时间复杂度优化至O(n2logn)O(n2logn)

• 这里我们采用双指针方法，可以继续降低时间复杂度。首先固定最大边的位置 i，然后在 [0, i-1]之间利用双指针找到满足条件的三边。时间复杂度为O(n2)O(n2)。

算法流程

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

• 从右向左遍历最大边，固定最大边的位置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(n2)O(n2)。外层遍历最大边是n，内层循环移动双指针是n，所以总复杂度为O(n2)O(n2)。

• 空间复杂度为O(1)O(1)，只需占用常量空间。

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;
        }

        Arrays.sort(S);

        int count = 0;
        for (int i = 2; i < S.length; i++) {
            count += getTriangleCount(S, i);
        }
        return count;
    }

    private int getTriangleCount (int[] S, int thirdIndex){
        int count = 0;

        int left = 0;
        int right = thirdIndex - 1;
        int thirdEdge = S[thirdIndex];
        int sum;
        while (left < right){
            sum = S[left] + S[right];
            if (sum > thirdEdge) {
                count += right-left;
                right--;
            } else {
                left++;
            }
        }
        return count;
    }
}