[LeetCode] 611. Valid Triangle Number

[frdmu]

Given an integer array nums, return the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

 

Example 1:

Input: nums = [2,2,3,4]
Output: 3
Explanation: Valid combinations are: 
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Example 2:

Input: nums = [4,2,3,4]
Output: 4

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

 
 

解法一：
排序+二分查找。
暴力法很简单，就是三重循环，枚举所有组合，判断其是否能组成三角形。但是通不过后面的测试用例，超时了。这就需要在暴力法的基础上优化一下子。如果对数组排序，使得a <= b <= c。则原来判定三角形的条件：

a + b > c
a + c > b
b + c > a

就只需要满足a + b > c即可，因为排序后，另外两个条件就肯定满足。由此，就可以用二重循环遍历所有的a, b，并在剩余的元素中运用二分查找，找到第一个不满足a + b > c的c即可。代码如下：

class Solution {
public:
    bool check(int a, int b, int c) {
        if (a == 0 || b == 0 || c == 0)
            return false;
        if (a + b > c)
            return true;
        return false;         
    }
    int searchC(vector<int>& nums, int start, int end, int target) {
        int left = start, right = end;
        
        while (left < right) {
            int mid = left + (right - left) / 2; 
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }

        return right;
    }
    int triangleNumber(vector<int>& nums) {
        int cnt = 0; 
        int n = nums.size();
        
        sort(nums.begin(), nums.end()); 
        for (int i = 0; i < n-2; i++) {
            for (int j = i+1; j < n-1; j++) {
                int tmp = searchC(nums, j+1, n, nums[i]+nums[j]);
                cnt += (tmp - j - 1); 
            }
        } 

        return cnt;
    }
};

解法二：
优化一下解法一，nums[j]增加，nums[k]也增加。代码如下：

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int n = nums.size();
        int res = 0;

        sort(nums.begin(), nums.end()); 
        for (int i = 0; i < n-2; i++) {
            int k = i+2; 
            for (int j = i+1; j < n-1; j++) {
                while (k < n && nums[i] + nums[j] > nums[k]) {
                    k++;
                }    
                res += max(k-j-1, 0);
            }
        }

        return res;

    }
};