來自排序序列的三角形數量

給定嚴格遞增的n正整數序列A(1) < A(2) < ... < A(n)。我們需要找到具有邊長的三角形的數量爲3這個序列的不同元素。來自排序序列的三角形數量

由於n <= 6000，檢查每個可能的組合不夠快。有沒有更好的算法？謝謝你的幫助。

我的僞代碼：

for i from 0 till n - 2 
    for j from i+1 till n-1 
     for k from j+1 till n 
      if A[i] + A[j] > A[k] then count += 1 
      else break

2015-10-29 Artur

什麼是你實際的算法能不能給？我們舉了一個例子嗎？ –

我在帖子中添加了我的psuedo-code。 – Artur

任何幫助？@JeanJung – Artur

2015-10-30 08:45:47 MBo

回答