统计数组中总和小于sum的三元组的数量

给定一个没有重复元素的数组，和一个sum值。统计数组中总和小于sum的三元组的数量。

例如对于数组nums[] = {-2, 0, 1, 3}，sum = 2，共有2个三元组的总和小于sum：(-2, 0, 1)和(-2, 0, 3)

本题类似3sum，虽然不是等于sum，但是解法类似。

1. 排序，此处可复习快排
2. 给定一个i，范围从0到size-2
3. 给两个index l和r，l的范围是从i向后，r的范围是从后向前，l和r不相交
4. 计算三个index对应的数字和，如果小于sum，则记录

func CountTripletsSmallerThanSum(num []int, k int) [][]int {
	sort.Ints(num)
	size := len(num)
	result := [][]int{}
	for i := 0; i < size-2; i++ {
		l := i + 1
		r := size - 1
		for l < r {
			if num[i]+num[l]+num[r] < k {
				result = append(result, []int{num[i], num[l], num[r]})
				l++
			} else {
				r--
			}
		}
	}
	return result
}

• 相关文章
• 全局相关文章