Leetcode - deepest-leaves-sum
Leetcode - 3sum-closest

Array- CountTripletsSmallerThanSum

violet posted @ Feb 25, 2020 06:22:32 AM in 算法 with tags Algorithm Golang Sort 3sum , 382 阅读

统计数组中总和小于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
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter