题解 | #合法的三角形个数#

package main

import (
	"sort"
)

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param nums int整型一维数组
 * @return int整型
 */
func validTriangleNumber( nums []int ) int {
    // write code here
    var sums [1010]int
    sort.Sort(sort.IntSlice(nums))
    for len(nums) > 0 && nums[0] ==0 {
        nums = nums[1:]
    }

    for i := 0; i< len(nums); i++ {
        sums[nums[i]]++
    }
    for i := 1; i < 1010; i++ {
        sums[i] += sums[i-1]
    }

    sum := 0
    last, lastNum := -1, 0
    for i := 0; i < len(nums); i++ {
        if nums[i] == last {
            lastNum++
        } else {
            last, lastNum = nums[i], 1
        }
        newLast, newLastNum := last, lastNum
        for j := i+1; j < len(nums); j++ {
            if nums[j] == newLast {
                newLastNum++
            } else {
                newLast, newLastNum = nums[j], 1
            }

            add := nums[i] + nums[j]-1
            if add > 1001 {
                add = 1001
            }
            sum += sums[add]

            sum -= newLastNum
            if nums[j] != 0 {
                sum -= sums[nums[j]-1]
            }
        }
    }
    return sum
}