题目：有效三角形的个数
给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。
示例 1:
1
2
3
4
5
6
7
| 输入: [2,2,3,4]
输出: 3
解释:
有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
|
注意:
数组长度不超过1000。
数组里整数的范围为 [0, 1000]。
分析：
首先，能够组成三角形三条边的条件是 a + b > c ，其中a和b为较小边，那就可以先将数组升序排序。
暴力解法是三重循环枚举数组，找出符合条件的组合并计数，时间复杂度O(n^3)
对于需要循环遍历的算法，有个常用的优化时间方法就是二分法，本题中前两个数字用循环遍历，最后一个数字使用二分法，时间复杂度O(n^2 * logn)
还可以进一步优化，就是双指针法，可以发现，如果我们固定 i，那么随着 j 的递增，不等式 nums[i]+ nums[j] 也是递增的，因此 k 也是递增的，这样一来，我们就可以将 j 和 k 看成两个同向（递增）移动的指针
在第一个数字的循环中，就定义最后一个数字，即第二个数字和最后一个数字都有各自的递增路线，只要找到各自符合的位置即可，时间复杂度O(n * (n + n) = O(n^2)
题解：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| class Solution {
public:
//排序 + 双指针法
int triangleNumber(vector<int>& nums) {
if(nums.size() < 3) return 0;
sort(nums.begin(), nums.end());
int ret = 0;
for(int i = 0; i <= nums.size() - 3; ++i){
int k = i + 2;
for(int j = i + 1; j <= nums.size() - 2; ++j){
while(k < nums.size() && nums[i] + nums[j] > nums[k]) k++;
ret += max(--k - j, 0);
}
}
return ret;
}
//排序 + 二分法
// int triangleNumber(vector<int>& nums) {
// if(nums.size() < 3) return 0;
// sort(nums.begin(), nums.end());
// int ret = 0;
// for(int i = 0; i <= nums.size() - 3; ++i){
// for(int j = i + 1; j <= nums.size() - 2; ++j){
// int k = j;
// int left = j + 1, right = nums.size() - 1;
// while(left <= right){
// int mid = (right - left) / 2 + left;
// if(nums[i] + nums[j] > nums[mid]) {
// left = mid + 1;
// k = mid;
// }
// else right = mid - 1;
// }
// ret += k - j;
// }
// }
// return ret;
// }
};
|
收获：
1.优化循环遍历可以用二分法
2.根据公式如何找出潜在的规律，逃出多重循环