返回信息流请各位大佬指点：
题目是输入大于等于1的三个整数，x，y，z，分别表示三条边的取值范围，比如x=3表示这条边可以取1或2或3，问能构成的三角形数，345和354算两个。然后xyz取值范围都是10^9所以不能遍历。
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #96512同步于 2018/9/17
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
腾讯算法笔试题-求三角形数目
nanguohao
2018/9/17镜像同步25 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
提个思路吧，对于给定的两条边x和y，假设x>y，那么第三条边满足x-y < z < x+y ，因此三角形数目为2y-1，也就是只和较小的边y相关.短时间只想到这里
感觉有点像【LeetCode】611. Valid Triangle Number
根据611题的思路，先确定这个三角形中最长的边，那么剩下两条边的要求是：两边之和大于最长边。
所以，我们只需要把每个输入当做最长边进行遍历，根据最长边来确定剩下两条边的范围。
比如输入的是100,80,70.
先把第一个输入当做最大边遍历：第一轮为100,第二条边的取值范围是31~80，第三条边的范围是21~70.当第二条边取值是80时，第三条边可以取21~70，共50个数；当第二条边取值是79时，第三条边可以取22~70，共49个数；……当第二条边取值是31时，第三条边可以取70，共1个数；所以第一轮总共有50+49+...+1个三角形，即(50 * 51) / 2个三角形。
第二轮最大边是99，第二条边的取值范围是30~80，第三条边的范围是20~70.有51+50+...+1个三角形。
然后循环下去吧。。
这是个简单的想法，估计还有问题。。望指正。
【 在 fuxuemingzhu 的大作中提到: 】
: 感觉有点像【LeetCode】611. Valid Triangle Number
: 根据611题的思路，先确定这个三角形中最长的边，那么剩下两条边的要求是：两边之和大于最长边。
: 所以，我们只需要把每个输入当做最长边进行遍历，根据最长边来确定剩下两条边的范围。
: ...................
厉害了~
一楼的思路如果直接用在遍历中应该是可以解出来的，但是因为取值最大10^9，遍历可能不行。
或许能得到一个公式或者缩小循环范围。
【 在 fuxuemingzhu 的大作中提到: 】
: 感觉有点像【LeetCode】611. Valid Triangle Number
: 根据611题的思路，先确定这个三角形中最长的边，那么剩下两条边的要求是：两边之和大于最长边。
: 所以，我们只需要把每个输入当做最长边进行遍历，根据最长边来确定剩下两条边的范围。
: ...................
如果我的思路对的话，你顺着我的思路继续推导一下？
总个数
= n*(n + 1)/2 + (n+1)*(n+2)/2 +... + m*(m+1)/2
= n/2 + (n + 1) + (n + 2) +... + m + (m + 1)/2
= (n + m + 1)/2 + n*(m-n) + sum(1...(m-n))
= (n + m + 1)/2 + n*(m-n) + (m - n)*(m -n + 1) / 2
这就是你要的公式吧
【 在 nanguohao 的大作中提到: 】
: 一楼的思路如果直接用在遍历中应该是可以解出来的，但是因为取值最大10^9，遍历可能不行。
: 或许能得到一个公式或者缩小循环范围。
是不是得用公式啊，反正暴力遍历3条边过30%，遍历两条边计算第三条边O(N^2)，过60%。 我感觉类似动态规划的思想能做吗？如果a,b,c满足三角形的话，是不是a+1,b+1,c+1也一定满足？如果是这样的话，直接遍历第一条边就可以把，f(n+1)除了f(n)以外，需要额外考虑下边界，例如2,3,4可以但是1,2,3不可以。这样就是O(n)了