【算法刷题】Day9_代码007(未授权)

本文介绍: 这个时候，我们想，如果让这个数组是有序的，对比的这三个边是有序的，那么两个较短的边相加，大于第三边，是不是就可以说明前面两条边任意一条和后面的相加，都大于其余一条边呢？让left + right，如果大于最后一个数字，那么left 右边的所有数字和 right 相加都大于，所以中间的统计下来，right –我们一般的判断都是任意两边之和大于第三边，但是如果在时间复杂度的位置上考虑，比三次太麻烦。我们先看这个数组，我们先把最后一个数字固定，定义 left 和 right，如果大于 t ，right–

在这里插入图片描述

原题链接

首先看题干，非负整数数组，三元组数
所以，我们可知，这个数组最少有三个元素，这样才能组成三元组

在解题之前，我们补充一点：
给我们三个数，怎么判断是不是能不能构成三角形呢？
我们一般的判断都是任意两边之和大于第三边，但是如果在时间复杂度的位置上考虑，比三次太麻烦
这个时候，我们想，如果让这个数组是有序的，对比的这三个边是有序的，那么两个较短的边相加，大于第三边，是不是就可以说明前面两条边任意一条和后面的相加，都大于其余一条边呢？
在这里插入图片描述
很明显，这样是可以的，所以我们的算法就进一步进行了优化

1、暴力枚举 O(N)
暴力算法就是写三个 fo r 循环嵌套，在最里面的一层 fo r 循环判断三个数是否能组成三角形

class Solution {
    public int triangleNumber(int[] nums) {
        //1.优化：排序
        Arrays.sort(nums);

        //2.利用双指针解决问题
        int ret = 0;
        int n = nums.length;
        for (int i = n - 1; i >= 2; i--) {//先固定最大的数
            //利用双指针快速统计处符合要求的三元组的个数
            int left = 0;
            int right = i-1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    ret += right - left;
                    right--;
                }else {
                    left++;
                }
            }
        }
        return ret;
    }
}

public int[] twoSum(int[] price, int target) {
        int left = 0;
        int right = price.length-1;
        while (left < right) {
            int sum = price[left] + price[right];
            if (sum > target) {
                right--;
            }else if (sum < target) {
                left++;
            }else {
                return new int[]{price[left],price[right]};
            }
        }
        return new int[]{0};
    }

public int tribonacci(int n) {
        //1.创建 dp 表
        //2.初始化
        //3.填表
        //4.返回值

        //先处理边界
        if(n == 0) {
            return 0;
        }
        if(n == 1 || n == 2) {
            return 1;
        }

        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = dp[2] = 1;
        for(int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        return dp[n];
    }

public int tribonacci(int n) {
        //空间优化

        //先处理边界
        if(n == 0) {
            return 0;
        }
        if(n == 1 || n == 2) {
            return 1;
        }

        int a = 0;
        int b = 1;
        int c = 1;
        int d = 0;
        for(int i = 3; i <= n; i++) {
            d = a + b + c;
            //滚动操作
            a = b;
            b = c;
            c = d;
        }
        return d;
    }