提高了找出用给定的棍子可以制作多少个可能的三角形的性能

Question

我正在进行一项评估，要求输入给定的“n”作为输入，即一根棍子的长度；你能拼出多少个三角形？（3 < n < 1,000,000）

例如：

input: N=8
output: 1
explanation:
(3,3,2)

input: N=12 
output: 3
explanation:
(4,4,4) (4,5,3) (5,5,2)

现在，我编写的代码返回了 33% 的准确度，因为网络评估抛出了时间限制错误。

ans = 0
n = int(input())
for a in range(1, n + 1):
   for b in range(a, n - a + 1):
    c = n - a - b
    if a + b > c >= b:
        ans += 1
print(ans)

代码b：

ans = 0
n = int(input())
for i in range(1,n):
 for j in range(i,n):
  for c in range(j,n):
     if(i+j+c==n and i+j>c):
           ans+=1
print(ans)

如何才能做得更快？

Answer 1

这是我想出的一个直观的 O(n) 算法：

def main():
  n = int(input())
  if n < 3:
    print(0)
    return
  ans = n % 2
  for a in range(2, n//2+1):
    diff = n - a
    if diff // 2 < a:
      break
    if diff % 2 == 0:
      b = diff // 2
    else:
      b = diff // 2 + 1
    b = max(b - a // 2, a)
    c = n - b - a
    if abs(b - c) >= a:
      b += 1
      c -= 1
    ans += abs(b-c)//2 + 1
  print(ans)

main()

我找到 和 的上限和下限b，c并计算该范围内的值。