leetcode-go/leetcode/medium/611.valid-triangle-number.go

func triangleNumber(nums []int) int {
	n, cnt := len(nums), 0
	sort.Ints(nums)
	m := make(map[int]int)
	for i := 0; i < n-2; i++ {
		for j := i + 1; j < n-1; j++ {
			sum := nums[i] + nums[j]
			if v, ok := m[sum]; ok {
				if j < v {
					cnt += v - j - 1
				}
			} else {
				beg, end := j, n-1 // Not j+1, but j
				for beg <= end {
					mid := beg + (end-beg)/2
					if nums[mid] < sum {
						beg = mid + 1 // So beg is the first idx that >= sum
					} else {
						end = mid - 1
					}
				}
				m[sum] = beg
				if j < beg {
					cnt += beg - j - 1
				}
			}
		}
	}
	return cnt
}