首页 > itarticle > 【leetcode】611. valid triangle number

【leetcode】611. valid triangle number

admin 11月 13, 2020 0

Description

Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example

Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are:
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Note

1.The length of the given array won’t exceed 1000.
2.The integers in the given array are in the range of [0, 1000].

Solution

First

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
public int (int[] nums) {
        Arrays.sort(nums);
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int first = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                int second = nums[j];
                for (int m = j + 1; m < nums.length; m++) {
                    int third = nums[m];
                    if (third >= first + second) {
                        break;
                    } else {
                        count++;
                    }
                }
            }
        }
        return count;
    }

Result

AC

Analyse

Brute force方法，复杂度撑到了O(n^3)。

Optimization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
public int (int[] nums) {
        Arrays.sort(nums);
        int count = 0;
        int len = nums.length;
        for (int i = len - 1; i > 1; i--) {
            int l = 0;
            int r = i - 1;
            while (l < r) {
                if (nums[l] + nums[r] > nums[i]) {
                    count += r - l;
                    r--;
                } else {
                    l++;
                }
            }
        }
        return count;
    }

Idea

这个思路就是界定边界，左边从0开始，右边从len-2开始，i从len-1开始，如果这个时候满足了nums[l]+nums[r]>nums[i]，那必然l从现在的index到r-1的index配合现在的r和i，都满足构成三角形的条件，复杂度降到了O(n^2)。

Analyse

暂时没有发现更低复杂度解法。

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能