algorithm - Determinate the existence of a triangle given a sorted list

Question

I have come across a problem about the determination of triangle, it says:

Given a sorted integer array(length n), determinate whether you could build a triangle by choosing three integers from the array, the answer is "yes" or "no".

A naive solution is by scanning all the possibilities but it turn out to be O(n^3), seems it will be C(n, 3) possibilities.

Answer 1

假设整数代表边长并且array(0) > 0，

bool IsTriangle(int[] aray, int start) {
  if(array.length - start <= 2) return false;

  return  (array(start+2) < array(start+1) + array(start+0)) 
      || IsTriangle(array,start+1);
}

这是有效的，因为整数列表是排序的；因此，使用数组的任何后续元素，RHS 将始终较大，而使用数组的任何先前元素，LHS 将始终较小，因此只有选择的三个连续元素满足三角不等式才能满足三角不等式。这当然是 O(n) 并且可以很容易地转换为（不太优雅但性能更高的）迭代解决方案。