题解 | #组装三角形#

1 先排序
2 三个指针 a b c

a 是固定的 b c是滑动指针
如果 arr[a] + arr[b] > arr[c] （三角形特性）
那么和 ab 能成功匹配的极限c值就是第一个大于等于arr[a] + arr[b] 的前一个位置 (由于排序的原因 这里就跳过了很多无效的匹配) 。 周而复始即可。

package main
import (
    "fmt"
    "sort"
)

func main() {
    var arr []int 
    var count int
    fmt.Scanln(&count)

    if count <  3 {
        fmt.Println(0)
        return
    }
    for i := 0; i < count; i++ {
        var num int 
        fmt.Scanf("%d", &num)
        arr = append(arr, num)
    }
    // 尺取
    sort.Ints(arr)
    ans := 0
    for i := 0; i < len(arr) - 2; i ++ {
        l, r := i + 1, i + 2
        for r < len(arr) {
            if r == l {
                r ++
                continue
            }
             // 任意两边和大于另一个边
            abSum := arr[i] + arr[l]
            if abSum > arr[r]  {
                mostLessRight := r
                for mostLessRight < len(arr) && arr[mostLessRight] < abSum {
                    mostLessRight ++
                }
                ans += mostLessRight - r 
                l ++
            }else {
                l ++
            }
        }
    }
    fmt.Println(ans)   
}