本文共 2212 字，大约阅读时间需要 7 分钟。
LeetCode题号：
问题描述：
小扣在秋日市集选择了一家早餐摊位，一维整型数组 staple 中记录了每种主食的价格，一维整型数组 drinks 中记录了每种饮料的价格。小扣的计划选择一份主食和一款饮料，且花费不超过 x 元。请返回小扣共有多少种购买方案。
注意：答案需要以 1e9 + 7 (1000000007) 为底取模，如：计算初始结果为：1000000008，请返回 1
示例 1：
输入：staple = [10,20,5], drinks = [5,5,2], x = 15
输出：6
解释：小扣有 6 种购买方案，所选主食与所选饮料在数组中对应的下标分别是：
第 1 种方案：staple[0] + drinks[0] = 10 + 5 = 15； 第 2 种方案：staple[0] + drinks[1] = 10 + 5 = 15； 第 3 种方案：staple[0] + drinks[2] = 10 + 2 = 12； 第 4 种方案：staple[2] + drinks[0] = 5 + 5 = 10； 第 5 种方案：staple[2] + drinks[1] = 5 + 5 = 10； 第 6 种方案：staple[2] + drinks[2] = 5 + 2 = 7。示例 2：
输入：staple = [2,1,1], drinks = [8,9,5,1], x = 9
输出：8
解释：小扣有 8 种购买方案，所选主食与所选饮料在数组中对应的下标分别是：
第 1 种方案：staple[0] + drinks[2] = 2 + 5 = 7； 第 2 种方案：staple[0] + drinks[3] = 2 + 1 = 3； 第 3 种方案：staple[1] + drinks[0] = 1 + 8 = 9； 第 4 种方案：staple[1] + drinks[2] = 1 + 5 = 6； 第 5 种方案：staple[1] + drinks[3] = 1 + 1 = 2； 第 6 种方案：staple[2] + drinks[0] = 1 + 8 = 9； 第 7 种方案：staple[2] + drinks[2] = 1 + 5 = 6； 第 8 种方案：staple[2] + drinks[3] = 1 + 1 = 2；
优化前：暴力破解，可惜耗时太久，无法通过官方测试。
优化后：采用排序+二分查找，staple数组中的所有数字以staple[i]-x为目标值在drinks中二分查找存在重复值，故二分搜索应查找最靠右的目标值。
优化前code：
func breakfastNumber(staple []int, drinks []int, x int) int { const NUMBER = 1000000007 var count int = 0 sort.Ints(staple) sort.Ints(drinks) for i := 0; i < len(staple); i++ { if staple[i] > x { break } for j := 0; j < len(drinks); j++ { if drinks[j] > x { break } if staple[i]+drinks[j] <= x { count++ } } } return count % NUMBER} 优化后code：
func breakfastNumber(staple []int, drinks []int, x int) int { const NUMBER = 1000000007 var count = 0 sort.Ints(staple) sort.Ints(drinks) for i := 0; i < len(staple); i++ { if staple[i] > x { break } var low = 0 var high = len(drinks) var target = x - staple[i] //采用二分查找 for j := len(drinks) - 1; j >= 0 && low < high; j-- { var mid = (low + high) / 2 //比目标值大，说明目标值在当前mid值左边，接着往左分 if drinks[mid] > target { high = mid } else { //比目标值小，往右+1查找 low = mid + 1 } } //找到小于等于目标值(target)的元素下标，即[0，low]中的值都满足。 count += low } return count % NUMBER} 【1】
❤如果文章对您有所帮助，就在文章的右上角或者文章的末尾点个赞吧！(づ￣ 3￣)づ
❤如果喜欢大白兔分享的文章，就给大白兔点个关注吧！(๑′ᴗ‵๑)づ╭❤～
❤对文章有任何问题欢迎小伙伴们下方留言或者入群探讨【群号：708072830】
❤鉴于个人经验有限，所有观点及技术研点，如有异议，请直接回复讨论(请勿发表攻击言论)
转载地址：http://sigvf.baihongyu.com/