69 三角形计数（Triangle Count）

文章目录1 题目2 解决方案2.1 思路2.2 时间复杂度2.3 空间复杂度3 源码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) 42 解决方案2.1 思路首先三条边在满足abc的前提下只要满足abc即可构成三角形这样我们先对数组进行排序使得按照位置取出来的三个数能够满足abc将c通过循环进行遍历固定再在c位置之前的子数组中找到和的值大于c的两个数即可。2.2 时间复杂度排序的时间复杂度O(n * log n)外层循环的时间复杂度为O(n)在子数组找两数和大于目标值的数的时间复杂度为O(n)总时间复杂度为O(n^2)。2.3 空间复杂度空间复杂度为O(1)。3 源码细节形成三角形的三边条件为(abc abc)即可。先进行排序让有序取出的abc满足abc再固定c去判断abc下标遍历固定c再two sum之前的区间若ab比c大则b不动a右移的所有ab都大于c加入结果之后b左移进行下一轮若ab比c小则需要a左移进行下一轮C版本/** * param S: A list of integers * return: An integer */ int triangleCount(vectorint S) { // write your code here int result 0; if (S.empty()) { return result; } // 先排序确保三个数的大小 abc 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指向aright指向b找到令 abc 的结果 int twoSumGreater(vectorint 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; }