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;
    }
}