611. Valid Triangle Number

LeetCode medium original: C# #array #csharp #leetcode #medium #search #sort #two-pointers

Task text is translated from Russian for the selected interface language. Code is left unchanged.

LeetCode Static

Если задан integer array nums, return количество выбранных из arrayа троек, которые могут образовывать треугольники, если принять их за длины сторон треугольника.

Example:

Input: nums = [2,2,3,4]

Output: 3

C# solution

matched/original

public class Solution {
    public int TriangleNumber(int[] nums) {
        Array.Sort(nums);
        int n = nums.Length;
        int count = 0;
        
        for (int k = n - 1; k >= 2; k--) {
            int i = 0;
            int j = k - 1;
            while (i < j) {
                if (nums[i] + nums[j] > nums[k]) {
                    count += j - i;
                    j--;
                } else {
                    i++;
                }
            }
        }
        
        return count;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int TriangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int count = 0;
        
        for (int k = n - 1; k >= 2; k--) {
            int i = 0;
            int j = k - 1;
            while (i < j) {
                if (nums[i] + nums[j] > nums[k]) {
                    count += j - i;
                    j--;
                } else {
                    i++;
                }
            }
        }
        
        return count;
    }
}

Java solution

matched/original

import java.util.Arrays;

public class Solution {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int count = 0;
        
        for (int k = n - 1; k >= 2; k--) {
            int i = 0;
            int j = k - 1;
            while (i < j) {
                if (nums[i] + nums[j] > nums[k]) {
                    count += j - i;
                    j--;
                } else {
                    i++;
                }
            }
        }
        
        return count;
    }
}

JavaScript solution

matched/original

function triangleNumber(nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let count = 0;
    
    for (let k = n - 1; k >= 2; k--) {
        let i = 0;
        let j = k - 1;
        while (i < j) {
            if (nums[i] + nums[j] > nums[k]) {
                count += j - i;
                j--;
            } else {
                i++;
            }
        }
    }
    
    return count;
}

Go solution

matched/original

package main

import (
    "sort"
)

func triangleNumber(nums []int) int {
    sort.Ints(nums)
    n := len(nums)
    count := 0
    
    for k := n - 1; k >= 2; k-- {
        i := 0
        j := k - 1
        for i < j {
            if nums[i] + nums[j] > nums[k] {
                count += j - i
                j--
            } else {
                i++
            }
        }
    }
    
    return count
}

Algorithm

Отсортируйте array nums.

Используйте три вложенных цикла: для каждого фиксированного третьего elementа, используйте два указателя для поиска подходящих первых двух elementов, которые удовлетворяют неравенству треугольника.

Увеличивайте счетчик на количество подходящих пар для каждого третьего elementа.

😎

Vacancies for this task

Active vacancies with overlapping task tags are shown.

All vacancies

There are no active vacancies yet.