有效三角形的个数 图解题解

这道题到底在问什么

输入

nums=[2,2,3,4]

输出

3

输入

nums=[4,2,3,4]

输出

4

输入

nums=[1,1,3]

输出

0（1+1 不大于 3）

先想最直接的笨办法

每个能当三元组最大边的位置(k 从 2 到 5)都固定过一遍、各跑一趟双指针,累计 11 个有效三角形,就是答案。回头看:排序 + 固定最大边 + 对撞双指针,把暴力枚举三元组的 O(n³) 压到了 O(n²)。（动画第 29 步）

最优解：一步一步想明白

1. 3记住「排序→固定最大边→对撞双指针:和够大就一次加 r−l 个、r 左移;不够就 l 右移」,下面每帧都在套它。
2. 4第一步排序。原数组是 [8, 2, 6, 4, 3, 5],排好序变成 [2, 3, 4, 5, 6, 8]。排序是后面双指针的前提:有了顺序,固定最右边那个就是当前最大边,左边的数也单调,指针才能稳稳对撞。
3. 5固定最大的那条边 nums[5]=8（黄色）。只要在它左边能找到两条边、和严格大于 8，就凑成一个三角形。左指针 l 从最左、右指针 r 紧挨最大边,往中间夹。
4. 6当前两条边是 nums[0]=2 和 nums[4]=6，它们的和是 8。下一步看这个和是不是严格大于最大边 8。
5. 78 没有大于 8，凑不成三角形。问题出在最小的那条边 nums[0]=2 太短,把它换掉:l 右移一格到 1,去试更大的最小边。
6. 8当前两条边是 nums[1]=3 和 nums[4]=6，它们的和是 9。下一步看这个和是不是严格大于最大边 8。
7. 99 严格大于 8，成立!这里有个关键省时:既然最小的 nums[1]=3 配 nums[4]=6 都够大,那把 l 换成 1 到 3 之间任何一个更大的数,配 nums[4] 和最大边一样成立,所以一次就能记下 r−l=3 个三角形。记完让 r 左移一格,去试更小的右边。
8. 10当前两条边是 nums[1]=3 和 nums[3]=5，它们的和是 8。下一步看这个和是不是严格大于最大边 8。
9. 118 没有大于 8，凑不成三角形。问题出在最小的那条边 nums[1]=3 太短,把它换掉:l 右移一格到 2,去试更大的最小边。
10. 12当前两条边是 nums[2]=4 和 nums[3]=5，它们的和是 9。下一步看这个和是不是严格大于最大边 8。
11. 139 严格大于 8，成立!这里有个关键省时:既然最小的 nums[2]=4 配 nums[3]=5 都够大,那把 l 换成 2 到 2 之间任何一个更大的数,配 nums[3] 和最大边一样成立,所以一次就能记下 r−l=1 个三角形。记完让 r 左移一格,去试更小的右边。
12. 14固定最大的那条边 nums[4]=6（黄色）。只要在它左边能找到两条边、和严格大于 6，就凑成一个三角形。左指针 l 从最左、右指针 r 紧挨最大边,往中间夹。
13. 15当前两条边是 nums[0]=2 和 nums[3]=5，它们的和是 7。下一步看这个和是不是严格大于最大边 6。
14. 167 严格大于 6，成立!这里有个关键省时:既然最小的 nums[0]=2 配 nums[3]=5 都够大,那把 l 换成 0 到 2 之间任何一个更大的数,配 nums[3] 和最大边一样成立,所以一次就能记下 r−l=3 个三角形。记完让 r 左移一格,去试更小的右边。
15. 17当前两条边是 nums[0]=2 和 nums[2]=4，它们的和是 6。下一步看这个和是不是严格大于最大边 6。
16. 186 没有大于 6，凑不成三角形。问题出在最小的那条边 nums[0]=2 太短,把它换掉:l 右移一格到 1,去试更大的最小边。
17. 19当前两条边是 nums[1]=3 和 nums[2]=4，它们的和是 7。下一步看这个和是不是严格大于最大边 6。
18. 207 严格大于 6，成立!这里有个关键省时:既然最小的 nums[1]=3 配 nums[2]=4 都够大,那把 l 换成 1 到 1 之间任何一个更大的数,配 nums[2] 和最大边一样成立,所以一次就能记下 r−l=1 个三角形。记完让 r 左移一格,去试更小的右边。
19. 21固定最大的那条边 nums[3]=5（黄色）。只要在它左边能找到两条边、和严格大于 5，就凑成一个三角形。左指针 l 从最左、右指针 r 紧挨最大边,往中间夹。
20. 22当前两条边是 nums[0]=2 和 nums[2]=4，它们的和是 6。下一步看这个和是不是严格大于最大边 5。
21. 236 严格大于 5，成立!这里有个关键省时:既然最小的 nums[0]=2 配 nums[2]=4 都够大,那把 l 换成 0 到 1 之间任何一个更大的数,配 nums[2] 和最大边一样成立,所以一次就能记下 r−l=2 个三角形。记完让 r 左移一格,去试更小的右边。
22. 24当前两条边是 nums[0]=2 和 nums[1]=3，它们的和是 5。下一步看这个和是不是严格大于最大边 5。
23. 255 没有大于 5，凑不成三角形。问题出在最小的那条边 nums[0]=2 太短,把它换掉:l 右移一格到 1,去试更大的最小边。
24. 26固定最大的那条边 nums[2]=4（黄色）。只要在它左边能找到两条边、和严格大于 4，就凑成一个三角形。左指针 l 从最左、右指针 r 紧挨最大边,往中间夹。
25. 27当前两条边是 nums[0]=2 和 nums[1]=3，它们的和是 5。下一步看这个和是不是严格大于最大边 4。
26. 285 严格大于 4，成立!这里有个关键省时:既然最小的 nums[0]=2 配 nums[1]=3 都够大,那把 l 换成 0 到 0 之间任何一个更大的数,配 nums[1] 和最大边一样成立,所以一次就能记下 r−l=1 个三角形。记完让 r 左移一格,去试更小的右边。
27. 29每个能当三元组最大边的位置(k 从 2 到 5)都固定过一遍、各跑一趟双指针,累计 11 个有效三角形,就是答案。回头看:排序 + 固定最大边 + 对撞双指针,把暴力枚举三元组的 O(n³) 压到了 O(n²)。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        ans = 0
        for k in range(len(nums) - 1, 1, -1):
            l, r = 0, k - 1
            while l < r:
                if nums[l] + nums[r] > nums[k]:
                    ans += r - l
                    r -= 1
                else:
                    l += 1
        return ans

#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = 0;
        for (int k = nums.size() - 1; k >= 2; --k) {
            int l = 0, r = k - 1;
            while (l < r) {
                if (nums[l] + nums[r] > nums[k]) { ans += r - l; r--; }
                else l++;
            }
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int ans = 0;
        for (int k = nums.length - 1; k >= 2; k--) {
            int l = 0, r = k - 1;
            while (l < r) {
                if (nums[l] + nums[r] > nums[k]) { ans += r - l; r--; }
                else l++;
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问