This is the 4th day of my participation in the August More Text Challenge

Leetcode -611- Number of valid triangles

[Blog link]

The path to learning at 🐔

The nuggets home page

[B].

Given an array of non-negative integers, your task is to count the number of triples that can form the three sides of a triangle.

Example 1:

Input: [2, 2, 3, 4]

Output: 3

Explanation:

The effective combination is:

2,3,4 (using the first 2)

2,3,4 (using the second 2)

2, 2, 3

Note:

• The length of the array cannot exceed 1000
• The range of integers in the array is [0, 1000]

Related Topics

• greedy
• An array of
• Double pointer
• Binary search
• The sorting
• 👍 👎 0 215

[答 案]

Leetcode topic link

[making address]

Code link

[introduction]

Idea 1: violent scan double pointer + binary search

• Sort the array first, then bisection the first two values on the right to find the largest element that satisfies
• A [I] + a[j] > a[mid]
• Mid-j is the quantity that satisfies

public int triangleNumber(int[] nums) {
            int res = 0;
            Arrays.sort(nums);
            for (int i = 0; i < nums.length; i++) {
                for (int j = i + 1; j < nums.length; j++) {
                    int l = j + 1, r = nums.length - 1, sum = nums[i] + nums[j];
                    int edge = check(nums, l, r, sum);
                    if (edge > 0) { res = res + edge - j; }}}return res;
        }

        private int check(int[] nums, int l, int r, int sum) {
            // There is no satisfying edge
            if (l == nums.length || nums[l] >= sum) {
                return -1;
            }
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (nums[mid] < sum) {
                    l = mid;
                } else {
                    r = mid - 1; }}return nums[r] == sum ? r - 1 : r;
        }
Copy the code

$Time complexity O(n^{2} LGN + NLGN)$

Sorting + double pointer + enumeration

• For numS [I] + NUMS [J]> NUMs [k];
• We can see that when fixed I scans
• J and K are not strictly positive correlation
• So as j increases, k stays the same or increases
• We can iterate over j and only judge if k is less than j

public int triangleNumber(int[] nums) {
    int n = nums.length;
    Arrays.sort(nums);
    int res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i - 1, k = 0; k < j; j--) {
            while(k < j && nums[k] + nums[j] <= nums[i]) { k++; } res += j - k; }}return res;
}
Copy the code

$Time complexity O(n^{2} + NLGN)$

extension

This is a very similar problemThe sum of three number, is also a hot topic, you can go to expand a ha