611. Valid Triangle Number (solution 1)

package LeetCode_611

/**
 * 611. Valid Triangle Number
 * https://leetcode.com/problems/valid-triangle-number/
 * 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.
Example 1:
Input: [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
Note:
The length of the given array won‘t exceed 1000.
The integers in the given array are in the range of [0, 1000].
 * */
class Solution {
    /*
    Because Triangle is the sum of any two sides must be greater than third sides (任意两条边之和要大于第三边),
    we need to find 3 numbers,i<j<k and nums[i]+nums[j]>nums[k];
      Solution 1: sort array, bruce force, Time:O(n^3), Space:O(1);
    * Solution 2: sort array, two pointer, Time:O(n^2), Space:O(1);
    * */
    fun triangleNumber(nums: IntArray): Int {
        if (nums == null || nums.isEmpty() || nums.size < 2) {
            return 0
        }
        var count = 0
        nums.sort()
        //solution 1
        val n = nums.size
        for (i in 0 until n - 2) {
            for (j in i + 1 until n - 1) {
                val sum = nums[i] + nums[j]
                var k = j + 1
                while (k < n && sum > nums[k]) {
                    count++
                    k++
                }
            }
        }
        return count
    }
}