摘要：
一道双指针题目。
题目
给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。
示例 1:
输入: [2,2,3,4]
输出: 3
解释:
有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
注意:
- 数组长度不超过 $1000$。
- 数组里整数的范围为 $[0, 1000]$。
双指针
构成三角形的条件是：三条边中，任意两条边之和大于第三条边。
我们可以将原数组排序，依次枚举最长边、次长边和最短边。其中，最长边从小到大枚举即可，次长边和最短边用两个指针维护。两个指针分别初始化为最长边左边第一个数下标和0. 次长边指针从右向左枚举，对于每一个次长边，将最短边指针从左到右枚举，直到找到最小的满足条件的最短边。因为数组是递增的，从最小的满足条件的最短边到次长边都是满足条件的。这样可以实现优化。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int triangleNumber(vector<int>& nums) {
int n = nums.size();
int res = 0;
sort(nums.begin(), nums.end());
for (int i = 0; i < n; i++) {
for (int j = i - 1, k = 0; j > 0 && k < j; --j) {
for (; k < j && nums[k] + nums[j] <= nums[i]; ++k);
res += j - k;
}
}
return res;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int triangleNumber(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = i - 1, k = 0; k < j && j > 0; --j) {
for (; k < j && nums[k] + nums[j] <= nums[i]; ++k);
res += j - k;
}
}
return res;
}
}
|
复杂度： 最坏情况下是 $n^2$，实际情况是每一个最长边，可能存在一段 $k$ 到 $j - 1$ 是满足条件的而不用遍历