LeetCode LCP 18. 早餐组合

Categories:

题目描述
思路分析
1. 解法一：排序 + 二分计数（推荐）
相似题目

题目描述

✅ LCP 18. 早餐组合

思路分析

解法一：排序 + 二分计数（推荐）

核心思路：

先排序饮料数组。

对每个主食价格 s，若 s < x，统计饮料中 <= x - s 的个数。

累加并对 1e9+7 取模。

复杂度分析：

时间复杂度：O(n log n)，其中 n 为数组长度。

空间复杂度：O(1) 额外空间（排序除外）。

import java.util.Arrays;

class Solution {
    private static final int MOD = 1_000_000_007;

    public int breakfastNumber(int[] staple, int[] drinks, int x) {
        Arrays.sort(drinks);
        long ans = 0;

        for (int s : staple) {
            if (s >= x) {
                continue;
            }
            int remain = x - s;
            int count = upperBound(drinks, remain);
            ans = (ans + count) % MOD;
        }

        return (int) ans;
    }

    private int upperBound(int[] arr, int target) {
        int l = 0;
        int r = arr.length;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (arr[m] <= target) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return l;
    }
}

import "sort"

func breakfastNumber(staple []int, drinks []int, x int) int {
	const mod = 1_000_000_007
	sort.Ints(drinks)
	ans := int64(0)

	for _, s := range staple {
		if s >= x {
			continue
		}
		remain := x - s
		count := upperBound(drinks, remain)
		ans = (ans + int64(count)) % mod
	}

	return int(ans)
}

func upperBound(arr []int, target int) int {
	l := 0
	r := len(arr)
	for l < r {
		m := l + (r-l)/2
		if arr[m] <= target {
			l = m + 1
		} else {
			r = m
		}
	}
	return l
}

相似题目

题目	难度	考察点
1099. 小于 K 的两数之和	简单	排序
167. 两数之和 II - 输入有序数组	中等	双指针
16. 最接近的三数之和	中等	排序
611. 有效三角形的个数	中等	双指针
259. 较小的三数之和	中等	双指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/79124591