611-有效三角形的个数.md

611-有效三角形的个数.md

原题

解法

一： 枚举

我们知道，对于给定的三个非负数 a, b, c，如果满足 a + b > c, a + c > b, b + c > a，那么 a, b, c 可以组成一个三角形。因此我们可以使用三重循环分别枚举 a, b, c，并检查是否满足上面的三个不等式。

const triangleNumber = function(nums) {
    let count = 0;
    for (let i = 0; i < nums.length - 2; i++) {
        for (let j = i + 1; j < nums.length - 1; j++) {
            for (let k = j + 1; k < nums.length; k++) {
                if (nums[i] + nums[j] > nums[k] && nums[i] + nums[k] > nums[j] && nums[j] + nums[k] > nums[i]) {
                    count++;
                }
            }
        }
    }
}

复杂度分析

• 时间复杂度 O(N³)，其中 N 是数组的长度
• 空间复杂度：O(1)

二：二分查找

先把代码放上来，感觉放代码上来就挺好懂的

const binarySearch = function(nums, l, r, x) {
    while (r >= l && r < nums.length) {
        const mid = (l + r) / 2;
        if (nums[mid] >= x) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

const triangleNumber = function(nums) {
    let count = 0;
    nums.sort((a, b) => a - b);

    for (let i = 0; i < nums.length - 2; i++) {
        let k = i + 2;
        for (let j = i + 1; j < nums.length - 1 && nums[i] != 0; j++) {
            k = binarySearch(nums, k, nums.length - 1, nums[i] + nums[j]);
            console.log(k, j)
            count += k - j - 1;
        }
    }

    return count;
}

三：双指针

在方法二中，我们固定位置 i, j 后，用二分查找的方法找出满足条件的 k。事实上，我们也可以使用双指针的方法，其中一个指针表示 j，另一个指针表示 k，来找出对于每一个 j，满足条件的 k 的数目。

我们使用一重循环枚举 i。j 的初始值为 i + 1，k 的初始值为 j + 1 = i + 2。对于每个固定的 j，我们增加 k 的值，直到有 nums[i] + nums[j] > nums[k]，此时 nums[j + 1] 到 nums[k - 1] 都满足条件，因此给答案加上 k - j - 1。随后我们将 j 的值增加 1，但 k 不用从 j + 1 开始增加，而是从上一次的 k开始增加即可。这样做的正确性在方法二中也有所表述，因为如果 nums[i] + nums[j] > nums[k] 成立，那么满足nums[i] + nums[j + 1] > nums[k1 + 1] 条件的 k1 一定不小于 k。在每一次循环中，我们只会将 j 和k 增加 O*(N) 次，因此时间复杂度为 O(N^2)*。

感觉代码挺好理解的，就是官方的说明还没有说懂，感觉就是官方的翻译质量不太行

const triangleNumber = function(nums) {
    let count = 0;
    nums.sort((a, b) => a - b);

    for (let i = 0; i < nums.length - 2; i++) {
        let k = i + 2;
        for (let j = i + 1; j < nums.length -1 && nums[i] != 0; j++) {
            // 因为已经在之前做过排序，所以在这里只需要比较一个条件就可以了
            while (k < nums.length && nums[i] + nums[j] > nums[k]) {
                k++;
                count += k - j - 1;
            }
        }
    }

    return count;
}

复杂度分析

• 时间复杂度： O(N²)，其中N是数组的长度
• 空间复杂度： O(logN), 为排序需要的空间