611. Valid Triangle Number #

Problem #

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.

Problem Summary #

Given an array containing non-negative integers, your task is to count the number of triplets that can form the three sides of a triangle.

Solution Approach #

• The idea is very simple. The most straightforward brute-force solution is three nested loops to enumerate all possibilities, with a time complexity of O(n^3). The innermost loop among the three nested loops can be optimized because k is related to i and j. The second loop j starts from i + 1, and k starts from j + 1 = i + 2. Keep incrementing k until nums[i] + nums[j] > nums[k]; then all values in the interval [nums[j + 1], nums[k - 1]] satisfy the condition. The number of valid solutions increases by k - j - 1. Then j increments by 1 again. At this point, the innermost k does not need to start from j + 1; it only needs to continue from the previous k. Because if nums[i] + nums[j] > nums[k], and if the inequality nums[i] + nums[j + 1] > nums[m + 1] holds, then m must be no smaller than k. Therefore, the combined time complexity of the inner loops k and j is O(n), and the outermost loop i is O(n). After this optimization, the overall time complexity is O(n^2).
• Some readers may have questions about the condition for forming a triangle with three sides: the sum of any two sides must be greater than the third side. a + b > c, a + c > b, b + c > a. Why do we only check a + b > c here? Because the array is sorted at the beginning, so a ≤ b ≤ c. Under this premise, a + c > b and b + c > a must hold. Therefore, the original problem is transformed into only needing to care whether the single inequality a + b > c holds. The test cases for this problem include a special case where one side or two sides have length 0, in which case the inequality a + b > c definitely does not hold. In summary, after sorting as preprocessing, we only need to care whether the inequality a + b > c holds.

Code #

package leetcode

import "sort"

func triangleNumber(nums []int) int {
	res := 0
	sort.Ints(nums)
	for i := 0; i < len(nums)-2; i++ {
		k := i + 2
		for j := i + 1; j < len(nums)-1 && nums[i] != 0; j++ {
			for k < len(nums) && nums[i]+nums[j] > nums[k] {
				k++
			}
			res += k - j - 1
		}
	}
	return res
}