Количество возможных треугольников с учетом массива чисел вопрос

Я пытаюсь найти количество возможных треугольников, которые можно сформировать с помощью набора чисел здесь:

https://www.geeksforgeeks.org/find-number-of-triangles-possible/

Я написал его версию на javaScript. однако я не совсем понимаю одну часть решения:

        // Total number of possible triangles that can  
        // be formed with the two fixed elements is 
        //  k - j - 1.  The two fixed elements are arr[i] 
        // and arr[j].  All elements between arr[j+1]/ to  
        // arr[k-1] can form a triangle with arr[i] and arr[j]. 
        // One is subtracted from k because k is incremented  
        // one extra in above while loop. 
        // k will always be greater than j. If j becomes equal 
        // to k, then above loop will increment k, because arr[k] 
        //  + arr[i] is always greater than arr[k] 

Проблема:

Я до сих пор не понимаю этой логики. Как k-j появился на свет?

Как такое количество треугольников, которое можно сформировать с помощью arr [i], arr [j] и arr [k] (с arr [i] <arr [j] <arr [k]), дает счет как k-j? неясно с этой стороны.

Может кто меня просветить?

JS-решение проблемы:

var triangleNumber = function(arr) {
       let count = 0, n = arr.length;

    //Sort the array in ascending order.
    arr.sort((a,b) => { return a-b; });

    // Set three pointers, i, j = i+1 and k=i+2
    for(let i=0; i<n-2; i++) {
        let k = i+2;
        for(let j=i+1; j<n; j++) {
            // If sum of two sides > third side
            /* Find the rightmost element which is smaller
				than the sum of two fixed elements
				The important thing to note here is, we use
				the previous value of k. If value of arr[i] +
				arr[j-1] was greater than arr[k], then arr[i] +
				arr[j] must be greater than k, because the
			array is sorted. */
            while (k <n && arr[i] + arr[j] > arr[k]) {
                ++k;
            }

            /* Total number of possible triangles that can be
				formed with the two fixed elements is k - j - 1.
				The two fixed elements are arr[i] and arr[j]. All
				elements between arr[j+1] to arr[k-1] can form a
				triangle with arr[i] and arr[j]. One is subtracted
				from k because k is incremented one extra in above
				while loop. k will always be greater than j. If j
				becomes equal to k, then above loop will increment
				k, because arr[k] + arr[i] is always/ greater than
				arr[k] */
            count += k-j-1;
        }
    }

    return count<0? 0: count;
};

const arr = [2,2,3,4];
console.info(triangleNumber(arr));

Ваш вопрос по математике или программе? Если дело в математике, Математика было бы лучшим местом.

Barmar 13.09.2018 02:09

Вы прочитали шаг 3 метода на странице, на которую ведет ссылка? Это объясняет, как k-j появляется на сцене.

Barmar 13.09.2018 02:10

@Barmar Я сделал. Однако я все еще не могу представить себе следующее утверждение Fix ‘i’ and ‘j’ and find the rightmost index ‘k’ (or largest ‘arr[k]’) such that ‘arr[i] + arr[j] > arr[k]’. The number of triangles that can be formed with ‘arr[i]’ and ‘arr[j]’ as two sides is ‘k – j’. Add ‘k – j’ to count of triangles.. Как мы можем доказать, что k-j - это счетчик? Цени свое время.

TechnoCorner 13.09.2018 02:27
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer
Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer
В настоящее время производительность загрузки веб-сайта имеет решающее значение не только для удобства пользователей, но и для ранжирования в...
Безумие обратных вызовов в javascript [JS]
Безумие обратных вызовов в javascript [JS]
Здравствуйте! Юный падаван 🚀. Присоединяйся ко мне, чтобы разобраться в одной из самых запутанных концепций, когда вы начинаете изучать мир...
Система управления парковками с использованием HTML, CSS и JavaScript
Система управления парковками с использованием HTML, CSS и JavaScript
Веб-сайт по управлению парковками был создан с использованием HTML, CSS и JavaScript. Это простой сайт, ничего вычурного. Основная цель -...
JavaScript Вопросы с множественным выбором и ответы
JavaScript Вопросы с множественным выбором и ответы
Если вы ищете платформу, которая предоставляет вам бесплатный тест JavaScript MCQ (Multiple Choice Questions With Answers) для оценки ваших знаний,...
0
3
430
1

Ответы 1

Элементы k-j начинаются от элемента после j до элемента k. Все они являются действительными третьими сторонами треугольника с arr[i] и arr[j] в качестве первых двух сторон.

Например. если первые две стороны - это arr[2] и arr[4], а наибольшая - k, где arr[i] + arr[j] > arr[k] - это 10, вы можете составить треугольник из k = 5, 6, 7, 8, 9, or 10. Там 6 индексов и 10 - 4 = 6.

Другие вопросы по теме