LeetCode611.有效三角形的个数

最近一直再刷PAT乙级，但总感觉乙级的题目有点简单......训练量不够。每天多刷一道LeetCode吧，希望自己在算法方面有进步！

题目

给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。

示例 1:

输入: [2,2,3,4]
输出: 3
解释:
有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

注意:

数组长度不超过1000。 数组里整数的范围为 [0, 1000]。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/valid-triangle-number 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

解法一：暴力枚举

• 遍历所有三条边的情况，判断能否成为三角形；
• 时间复杂度为\(O(n^3)\)，试了一下超时了，GG，换思路。

代码

class Solution
{
public:
    bool isTriangle(int a, int b, int c)
    {
        if (a + b > c && a + c > b && b + c > a && a - b < c && a - c < b && b - c < a)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    int triangleNumber(vector<int> &nums)
    {
        int count = nums.size();
        int res = 0;
        for (int i = 0; i <= count - 3; i++)
        {
            for (int j = i + 1; j <= count - 2; j++)
            {
                for (int k = j + 1; k < count; k++)
                {
                    if (isTriangle(nums[i], nums[j], nums[k]))
                    {
                        res++;
                    }
                }
            }
        }
        return res;
    }
};

解法二：排序+二分查找

该解法来自力扣官方解法。

对于正整数 \(a, b, c\)​​，他们可以作为三角形的三条边，当且仅当： \[ \left\{ \begin{aligned} &\text{ a + b > c}\\ &\text{ a + c > b}\\ &\text{ b + c > a} \end{aligned} \right. \] 均成立。如果我们将三条边进行升序排序，使他们满足 \(a≤b≤c\) ，那么 \(a + c > b\) 和 \(b + c > a\) 一定成立。那么只需要保证 \(a + b > c\) 就一定可以构成三角形。

那么，首先我们要对nums数组进行升序排序，然后使用二重循环枚举a和b。设a = nums[i], b = nums[j]，为了防止重复答案，显而易见要保证j > i。剩下的边c需要满足c < a + b即c < nums[i] + nums[j]。那么在[j + 1, n - 1]的下标范围使用二分查找，找到最大的下标k满足nums[k] < nums[i] + nums[j]，那么，在[j + 1, k]范围内的下标都可以作为c的下标，将该范围的长度k - (j + 1) + 1 = k - j累加进答案即可。枚举完成后，返回累加的答案即完成解答。

细节

题目中描述的nums包含的元素为非负整数，即除了正整数以外，nums还会包含0。但如果我们将nums进行升序排序，那么在枚举a和b时出现了0，那么nums[i]一定为0。此时，边c需要满足c < nums[i] + nums[j] = nums[j]，而下标在[j + 1, n - 1]范围内的元素一定都是大于等于nums[j]的，因此二分查找会失败。若二分查找失败，我们可以令k = j，此时对饮的范围长度k - j = 0，我们也就保证了答案的正确性。

代码

class Solution
{
public:
    int triangleNumber(vector<int> &nums)
    {
        int count = nums.size();
        int res = 0;
        sort(nums.begin(), nums.end());
        for (int i = 0; i <= count - 3; i++)
        {
            for (int j = i + 1; j <= count - 2; j++)
            {
                int left = j + 1, right = count - 1, k = j;
                // 二分查找
                while (left <= right)
                {
                    int mid = (left + right) / 2;
                    if (nums[mid] < nums[i] + nums[j])
                    {
                        k = mid;
                        left = mid + 1;
                    }
                    else
                    {
                        right = mid - 1;
                    }
                }
                res += k - j;
            }
        }
        return res;
    }
};

二分查找是一个很有用的算法，我明白其原理但是好像很少编过这个代码，导致有思路但代码却不会写，这可是程序员一大忌！！！

记录一下二分查找的一般形式：

public class BinarySearch {
    private int[] array;

    /**
     * 初始化数组
     * @param array
     */
    public BinarySearch(int[] array) {
        this.array = array;
    }

    /**
     * 二分查找
     * @param target
     * @return
     */
    public int search(int target) {
        if (array == null) {
            return -1;
        }

        int start = 0;
        int end = array.length - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (array[mid] == target) {
                return mid;
            } else if (target < array[mid]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return -1;
    }
}

二分查找（折半查找）算法（原理、实现及时间复杂度） (biancheng.net)