Algorithms & Data Structures : LeetCode 611. Valid Triangle Number

題目：

Valid Triangle Number - LeetCode

我的解法：

Time : O(N²logN)

/*
1. sort
2. 遍尋前兩數，用二分搜找最後一數
 */
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        if(nums.size() < 3) {
            return 0;
        }
        
        sort(nums.begin(), nums.end());
        int res = 0;
        
        for(int i = 0;i < nums.size() - 2;i++) {
            for(int j = i + 1;j < nums.size() - 1;j++) {
                int left = j + 1;
                int right = nums.size() - 1;
                int maxVal = INT_MIN;
                
                while(left <= right) {
                    int mid = (left + right) / 2;
                    if(nums[i] + nums[j] > nums[mid]) {
                        maxVal = max(maxVal, mid);
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
                
                if(maxVal != INT_MIN) {                
                    res += (maxVal - (j + 1) + 1);
                }
            }
        }
        
        return res;
    }
};

更好的解法：

Time : (N²)

這是寫在 LeetCode 詳解裡的寫法 XD，原本有想到用 two pointers 可是不知道該怎麼用，所以只想到比較直白的 binary search 解法，直到看到解答...

遍尋第一個數，再來同時遍尋第二個數以及第三個數。
乍看之下是 Time: O(N³) ，但因為第三個數不會重複遍尋的關係，所以可使用 two pointers 來讓時間複雜度達到 O(N²)

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