题目
小扣在秋日市集选择了一家早餐摊位，一维整型数组 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；
提示：
1 <= staple.length <= 10^5 1 <= drinks.length <= 10^5 1 <= staple[i],drinks[i] <= 10^5 1 <= x <= 2*10^5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/2vYnGI
分析
暴力法
直接双层循环，来遍历就好了
int breakfastNumber(int* staple, int stapleSize, int* drinks, int drinksSize, int x) { int i = 0; int j = 0; int count = 0; for(i = 0; i < stapleSize; i++) { for(j = 0; j < drinksSize; j++) { if(x >= staple[i] + drinks[j]) { count++; count = count % 1000000007; } } } return count; }
很显然，结果超时
排序 + 双指针
其实我们很容易想到先排序，然后再进行查找后遍历。来优化算法。
这里使用C语言库函数qsort，时间复杂度为On*log (n)，我们写的遍历时间复杂度为O(n2)
int compare_int(const void* e1, const void* e2) //比较函数 { return *(int*)e1 - *(int*)e2; } int breakfastNumber(int* staple, int stapleSize, int* drinks, int drinksSize, int x) { int i = 0; int j = 0; int count = 0; int start = 0; int end = 0; int mid = 0; // 调用<stdlib.h>库函数 排序函数 qsort(staple, stapleSize, sizeof(staple[0]), compare_int); qsort(drinks, drinksSize, sizeof(drinks[0]), compare_int); for (i = 0; i < stapleSize && staple[i] < x; i++) { for(j = 0; j < drinksSize && drinks[j] <= x - staple[i]; j++) { count++; count = count % 1000000007; } } return count; }
居然还超时，我们再想想，这里我们没有考虑到排序后的数据是有序的特性。接下来我们通过二分法继续优化。
排序 + 二分法
我们根据staple的值只需要找到drinks数组中临界值。通过drinks的下标就可以一次知道了，前面都是符合的值，那么我们就可以用二分法来查找第一个不符合的。但是这里还有一个小坑，如果所有数据都成立那么通过二分法得到的也仅仅为下标最大值，所以这里我们可以把所有数据都成立的情况特殊列出来。
这样我们的时间复杂度就是O (log 2 n)与qsort库函数复杂度相同。空间复杂度为1.
int compare_int(const void* e1, const void* e2) //升序排序的比较函数 { return *(int*)e1 - *(int*)e2; } int breakfastNumber(int* staple, int stapleSize, int* drinks, int drinksSize, int x) { int i = 0; int j = 0; int count = 0; int start = 0; int end = 0; int mid = 0; // 调用<stdlib.h>库函数 排序函数 qsort(staple, stapleSize, sizeof(staple[0]), compare_int); qsort(drinks, drinksSize, sizeof(drinks[0]), compare_int); for (i = 0; i < stapleSize && staple[i] < x; i++) { //考虑到最优情况(特殊情况) 所有数据都符合就直接终止 if (drinks[drinksSize - 1] <= x - staple[i]) { count += drinksSize; continue; } start = 0; end = drinksSize - 1; while (start < end) { mid = (start + end) / 2; if (drinks[mid] <= x - staple[i]) { start = mid + 1; } else { end = mid; } } count += start; count = count % 1000000007; } return count; }
功夫不负有心人，终于能跑了。这里我又想到一个点，俩个数组的值都是逐渐增大，而x不变。所以drinks数组的上限end应该小于等于上一个上限。
排序 + 优化二分法
俩个数组的值都是逐渐增大，而x不变。所以drinks数组的上限end应该小于等于上一个上限。如果没懂建议多读几遍。所以我们可以再增加一个变量来记录上次的上限用于更新。
int compare_int(const void* e1, const void* e2) //升序排序的比较函数 { return *(int*)e1 - *(int*)e2; } int breakfastNumber(int* staple, int stapleSize, int* drinks, int drinksSize, int x) { int i = 0; int j = 0; int count = 0; int start = 0; int end = 0; int mid = 0; int upper = drinksSize - 1; // 用于记录上次所取区间的上限 int len = 0; // 计算相同价格的主食有几种 // 调用<stdlib.h>库函数 排序函数 qsort(staple, stapleSize, sizeof(staple[0]), compare_int); qsort(drinks, drinksSize, sizeof(drinks[0]), compare_int); for (i = 0; i < stapleSize && staple[i] < x; i++) { // 考虑到最优情况 所有数据都符合就直接终止 if (drinks[drinksSize - 1] <= x - staple[i]) { count += drinksSize; continue; } // 正常情况 start = 0; end = upper; mid = (start + end) / 2; while (start < end) { if (drinks[mid] <= x - staple[i]) { start = mid + 1; } else { end = mid; } mid = (start + end) / 2; } count += start; upper = end; count = count % 1000000007; } return count; }
排序 + 二次优化二分法
上面优化了drinks数组，同样是不是可以优化staple数组？是的。我们可以将staple相同的数据统计起来一次计算。这里我们又增加了len一个变量，用来计算staple数组中重复的数据。
int compare_int(const void* e1, const void* e2) //升序排序的比较函数 { return *(int*)e1 - *(int*)e2; } int breakfastNumber(int* staple, int stapleSize, int* drinks, int drinksSize, int x) { int i = 0; int j = 0; int count = 0; int start = 0; int end = 0; int mid = 0; int upper = drinksSize - 1; // 用于记录上次所取区间的上限 int len = 0; // 计算相同价格的主食有几种 // 调用<stdlib.h>库函数 排序函数 qsort(staple, stapleSize, sizeof(staple[0]), compare_int); qsort(drinks, drinksSize, sizeof(drinks[0]), compare_int); for (i = 0; i < stapleSize && staple[i] < x; i++) { len = 1; while (i < stapleSize - 1 && staple[i] == staple[i + 1]) { i++; len++; } // 考虑到最优情况 所有数据都符合就直接终止 if (drinks[drinksSize - 1] <= x - staple[i]) { count += drinksSize * len; continue; } // 正常情况 start = 0; end = upper; mid = (start + end) / 2; while (start < end) { if (drinks[mid] <= x - staple[i]) { start = mid + 1; } else { end = mid; } mid = (start + end) / 2; } count += start * len; upper = end; count = count % 1000000007; } return count; }
空间换时间，复杂度直接降为O(n)
因为早餐的价格均为整数，我们有x的资金。即我们早餐主食的选择有：1 2 3 … x-1。我们可以用一个n[x]的数组来实现，数组中存放的是当前下标价位的早餐种类。一次遍历主食staple数组，获取到符合要求的主食种类。当我们主食价格为2元的搭配都符合时，那么主食为1元的也不是符合吗？
所有我们还需要遍历一次，n[i] += n[i - 1] + n[i - 2] + ... n[1];
最后我们只需要对drinks数组遍历，n[x - drinks[i]]里面存放的值就是当前饮料对应主食的种类。
让我们实现吧。
int breakfastNumber(int* staple, int stapleSize, int* drinks, int drinksSize, int x) { int n[x]; int i = 0; int count = 0; memset(n, 0, sizeof(int) * x); // 将主食价格小于x的放入数组对应的下标，下标里面放的数字表示当前下标出现的次数 for(i = 0; i < stapleSize; i++) { if(staple[i] < x)//主食价格小于总金额 { n[staple[i]]++; } } // 因为前面的价格必然小于等于后面的价格，也就是只要符合当前下标的话，你前面也都符合， // 所以我们直接累加。假如现在主食8元。n[8]中放的是主食{1...8}的所有种数 for(i = 2; i < x; i++) { n[i] += n[i - 1]; } for(i = 0; i < drinksSize; i++) { if(x - drinks[i] > 0) { count += n[x - drinks[i]]; count = count % 1000000007; } } return count; }
这样我们的时间复杂度只有O(n),空复杂度也为O(n)
本章完！
