69 三角形计数（Triangle Count）

1 题目

题目：三角形计数（Triangle Count）
描述：给定一个整数数组，在该数组中，寻找三个数，分别代表三角形三条边的长度，问，可以寻找到多少组这样的三个数来组成三角形？

lintcode题号——382，难度——medium

样例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

2 解决方案

2.1 思路

首先三条边在满足a<=b<=c的前提下，只要满足a+b>c即可构成三角形，这样我们先对数组进行排序，使得按照位置取出来的三个数能够满足a<=b<=c，将c通过循环进行遍历固定，再在c位置之前的子数组中找到和的值大于c的两个数即可。

2.2 时间复杂度

排序的时间复杂度O(n * log n)，外层循环的时间复杂度为O(n)，在子数组找两数和大于目标值的数的时间复杂度为O(n)，总时间复杂度为O(n^2)。

2.3 空间复杂度

空间复杂度为O(1)。

3 源码

细节：

1. 形成三角形的三边条件为(a<b<c && a+b>c)即可。
2. 先进行排序，让有序取出的abc满足a<b<c，再固定c去判断a+b>c（下标遍历固定c，再two sum之前的区间）
3. 若a+b比c大，则b不动，a右移的所有a+b都大于c，加入结果之后，b左移进行下一轮
4. 若a+b比c小，则需要a左移，进行下一轮

C++版本：

/** * @param S: A list of integers * @return: An integer */ int triangleCount(vector<int> &S) { // write your code here int result = 0; if (S.empty()) { return result; } // 先排序，确保三个数的大小 a<=b<=c sort(S.begin(), S.end()); // 固定c的位置 for (int i = 2; i < S.size(); i++) { int target = S.at(i); int temp = twoSumGreater(S, 0, i - 1, target); // 找到子数组中令两数和大于目标值的结果个数 result += temp; } return result; } // left指向a，right指向b，找到令 a+b>c 的结果 int twoSumGreater(vector<int> & S, int left, int right, int target) { int result = 0; while (left < right) { if (S.at(left) + S.at(right) <= target) { left++; } else if(S.at(left) + S.at(right) > target) { result = result + (right - left); // 直接将left左移的所有结果加入 right--; } } return result; }