[leetcode]611. Valid Triangle Number

Analysis

中午吃啥—— [每天刷题并不难0.0]

Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Explanation:

第一种方法就是暴力解决，直接遍历，然后判断，时间复杂度是O(n^3)。
第二种方法用了双指针，时间复杂度是O(n^2)。

Implement

方法一：

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int res = 0;
        int len = nums.size();
        sort(nums.begin(), nums.end());
        for(int i=0; i<len; i++){
            for(int j=i+1; j<len; j++){
                for(int k=j+1; k<len; k++){
                    if(nums[i]+nums[j] > nums[k])
                        res++;
                }
            }
        }
        return res;
    }
};

方法二：

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int res = 0;
        int len = nums.size();
        sort(nums.begin(), nums.end());
        for(int i=len-1; i>=2; i--){
            int l=0, r=i-1;
            while(l<r){
                if(nums[l]+nums[r] > nums[i]){
                    res += r-l;
                    r--;
                }
                else
                    l++;
            }
        }
        return res;
    }
};