Array- CountTripletsSmallerThanSum
统计数组中总和小于sum的三元组的数量
给定一个没有重复元素的数组，和一个sum值。统计数组中总和小于sum的三元组的数量。
例如对于数组nums[] = {-2, 0, 1, 3}，sum = 2，共有2个三元组的总和小于sum：(-2, 0, 1)和(-2, 0, 3)
本题类似3sum，虽然不是等于sum，但是解法类似。
- 排序，此处可复习快排
- 给定一个i，范围从0到size-2
- 给两个index l和r，l的范围是从i向后，r的范围是从后向前，l和r不相交
- 计算三个index对应的数字和，如果小于sum，则记录
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | 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} |
评论 (0)
