本文共 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】

❤鉴于个人经验有限，所有观点及技术研点，如有异议，请直接回复讨论(请勿发表攻击言论)

转载地址：https://luoyong.blog.csdn.net/article/details/108579228 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！