哔哩哔哩 2019秋招编程题---山寨金闪闪

 分析：这是一道关于能否构成三角形的题目

构成三角形的条件：a+b>c（前提a<=b<=c，也就是排序）再加上a>0&&b>0&&c>0（题目不存在异常数据不考虑）

 所以按照题目要求直接升序排序之后再判断a[i]+a[i+1]>a[i+2]，如果存在直接数量加1

解释一下为什么是a[i]+a[i+1]>a[i+2]就可以判断，有没有情况是a[i]+a[i+1]>a[i+2]不满足但是还存在三角形呢？

升序之后的数组如果存在a[i]+a[i+x]>a[i+y],(x>y>=2),也就是随机取得三个数如果满足三角形的条件

那么一定存在a[i]+a[i+y-1]>a[i+y],(因为是升序的，下标越大数字越大，下标i+y-1>=i+x,所以a[i+y-1]>=a[i+x],等式依然成立)

同理a[i+y-2]>=a[i],所以必定存在a[i+y-2]+a[i+y-1]>a[i+y]，也就是a[i]+a[i+1]>a[i+2]必定存在。。

注意：题目并没有要求求出【l,r】区间有多少三角形所以不要做多余的工作

c++代码如下：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=(int)1e7 + 5;
int n,a[MAXN],m;
vector<int>v;
int main() {
    while(~scanf("%d",&n)) {
        for(int i=1; i<=n; i++)scanf("%d",&a[i]);
        scanf("%d",&m);
        int cnt=0;
        while(m--) {
            int l,r;
            scanf("%d%d",&l,&r);
            if(r-l+1>=47)cnt++;//因为区间一旦很大就很容易构成三角形，别人测试出来的边界 
            else if(r-l+1<3)continue;
            else {
                v.clear();
                for(int i=l; i<=r; i++)v.push_back(a[i]);
                sort(v.begin(),v.end());
                int len=v.size();
                bool flag=0;
                for(int i=0; i<len-2; i++) {
                    if(v[i]+v[i+1]>v[i+2]) {
                        flag=1;
                        break;
                    }
                }
                if(flag)cnt++;
            }
        }
        printf("%d
",cnt);
    }
    return 0;
}

举一反三：

现在要求统计数组区间可以构成多少三角形。这是leetcode的一道题目：https://leetcode-cn.com/problems/valid-triangle-number/?utm_source=LCUS&utm_medium=ip_redirect_q_uns&utm_campaign=transfer2china

c++代码如下：

class Solution {//题目思想：固定c，左右变量分别再c的左侧滑动
public:
    int triangleNumber(vector<int>& nums) {
        int count = 0, size = nums.size();
        sort(nums.begin(), nums.end());
        for (int i = size - 1; i >= 2; i--) {//num[i]是c
            int left = 0, right = i - 1;//num[left]是a，num[right]是b
            while(left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    count += (right - left);//应该不用解释吧
                    right--;//计算出现在b的所有三角形，b左移
                }
                else {
                    left++;//和太小，a右移
                }
            }
        }
        return count;
    }
};