Leetcode611. 有效三角形的个数 Valid Triangle Number(Medium)

611. Valid Triangle Number(Medium)

##Array##, ##Two Pointers##

暴力法 O ( n 3 ) O(n^3) O(n3)

分别枚举三条边，记录可行的方案，该解法会超时

优化暴力法 O ( n 3 × l o g n ) O(n^3\times logn) O(n3×logn)

首先对数组进行排序，每条边都从小到大枚举，枚举第三条边时，遇到 第 一 条 边 第 二 条 边 ≤ 第 三 条 边 第一条边 第二条边 \le 第三条边 第一条边 第二条边≤第三条边时，不必继续枚举第三条边，因为第三条边继续向右枚举时，仍无法满足两边之和大于第三边

class Solution {
    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; j < n; j   ) {
                for (int k = j   1; k < n; k   ) {
                    if (nums[i]   nums[j] > nums[k]) res   ;
                    else break;
                }
            }
        }

        return res;

    }
}

二分优化暴力法 O ( n 2 × l o g 2 n ) O(n^2\times log^2{n}) O(n2×log2n)

同上方案，在找第三条边时，利用单调性使用二分找到满足两边之和大于第三边的最大第三边

class Solution {
    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; j < n; j   ) {
                int l = j   1, r = n - 1;
                while (l < r) {
                    int mid = l   r   1 >> 1;
                    if (nums[i]   nums[j] > nums[mid]) l = mid;
                    else r = mid - 1;
                }
                if (nums[i]   nums[j] > nums[r]) res  = r - j;
            }
        }
        return res;
    }
}

双指针 O ( n 2 ) O(n^2) O(n2)

class Solution {
    public int triangleNumber(int[] nums) {
        int n = nums.length;

        Arrays.sort(nums);
        int res = 0;
        for (int i = n - 1; i >= 2; i --) {
            int left = 0, right = i - 1;
            while (left < right) {
                if (nums[left]   nums[right] > nums[i]) {
                    res  = right - left;
                    right --;
                } else {
                    left   ;
                }
            }
        }
        return res;
    }
}

来源：https://www.icode9.com/content-4-906951.html