Как узнать, что треугольник-тройка существует в нашем массиве?

Question

Я застрял в решении следующего вопроса о практике интервью:
Мне нужно написать функцию:

int triangle(int[] A);

, для которой задан индексированный нулем массив A, состоящий из N целых чисел, возвращает 1 если существует тройка (P, Q, R) такая, что 0 < P < Q < R < N.

A[P] + A[Q] > A[R],  
A[Q] + A[R] > A[P],  
A[R] + A[P] > A[Q].

Функция должна возвращать 0, если такой тройки не существует.Предположим, что 0 < N < 100,000.Предположим, что каждый элемент массива представляет собой целое число в диапазоне [-1,000,000..1,000,000].

Например, данный массив A такой, что

A[0]=10, A[1]=2, A[2]=5, A[3]=1, A[4]=8, A[5]=20

функция должна возвращать 1, посколькутройка (0, 2, 4) удовлетворяет всем необходимым условиям.

Для массива A, для которого

A[0]=10, A[1]=50, A[2]=5, A[3]=1

, функция должна вернуть 0.

Если ясделать тройной цикл, это будет очень очень медленно (сложность: O(n^3)).Я думаю, может быть, использовать для хранения дополнительной копии массива и сортировки его, а также использовать двоичный поиск для определенного числа.Но я не знаю, как решить эту проблему.
Есть идеи?

Answer 1

Python:

def solution(A):
    A.sort()
    for i in range(0,len(A)-2):
        if A[i]+A[i+1]>A[i+2]:
            return 1
    return 0

Сортировка: логлинеарная сложность O (N log N)

Answer 2

100/100 php решение: http://www.rationalplanet.com/php-related/maxproductofthree-demo-task-at-codility-com.html

function solution($A) {
    $cnt = count($A);
    sort($A, SORT_NUMERIC);
    return max($A[0]*$A[1]*$A[$cnt-1], $A[$cnt-1]*$A[$cnt-2]*$A[$cnt-3]);
}

Answer 3

В ruby ​​насчет

def check_triangle (_array)
  for p in 0 .. _array.length-1
    for q in p .. _array.length-1
      for r in q .. _array.length-1
        return true if _array[p] + _array[q] > _array[r] && _array[p] + _array[r] > _array[q] && _array[r] + _array[q] > _array[p]
      end
    end
  end

  return false
end

Просто перенесите его на язык по вашему выбору