> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/7.two-pointers/382triangle-count/611.-valid-triangle-number.md).

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