达到累计收益目标的最短窗口
Shortest Window Hitting a Cumulative Return Target
开始编码你在评估一个最小持仓周期的收益目标:给定单一标的的逐日收益序列 returns,以及目标累计收益 target_cum_return,求历史上最短的连续窗口(连续若干个交易日)使得这一段的收益之和达到目标。这是周期预算类问题里很常见的 sanity check:「历史上最少需要多少个连续交易日才能累计涨到 ≥5%?」——在落地一个对路径长度敏感(比如最大回撤敏感)的策略前,先看看这个数。
请实现 solution(returns: list[float], target_cum_return: float) -> int。返回最小整数长度 L ≥ 1,使得存在某个长度为 L 的连续窗口满足 sum(returns[i:i+L]) ≥ target_cum_return。如果没有任何连续窗口能达到目标,返回 -1。当 returns 为空时同样返回 -1。
示例 1:solution([0.05, -0.02, 0.03, 0.04, -0.01], 0.04) 返回 1。第 0 天单日收益 0.05 ≥ 0.04,长度 1 的窗口已达标。示例 2:solution([0.01, 0.01, 0.01, 0.01, 0.01], 0.025) 返回 3。单日 0.01 不够,两日最大 0.02 还是不够,三日 0.03 ≥ 0.025,所以最短窗口长度为 3。示例 3:solution([0.01, 0.02, 0.03], 1.0) 返回 -1。整段 6% 远不够 100%,任何长度都不行。
关键结构性观察:判定式 P(L) := "存在长度 ≤ L 的窗口使其和 ≥ target_cum_return" 关于 L 是单调非降的——长度 L′ 下成立的窗口,在允许上限放宽到 L > L′ 时仍然成立(就是同一段窗口)。这种单调性正是「答案二分(binary-search-on-answer)」可以使用的条件:在 L ∈ [1, n] 上二分,找到最小的使 P(L) = True 的 L。每次判定 O(n)(前缀和 + 单调队列维护滑动最小值),共 O(log n) 次,总复杂度 O(n log n)。对比朴素的「从 L=1 到 n 逐个跑滑窗」O(n²),在 n = 10⁵ 时大致快了三个数量级。
约束条件
- 1 ≤ len(returns) ≤ 100000(空数组 → -1)
- -1.0 ≤ returns[i] ≤ 1.0(每日算术收益)
- -1000.0 ≤ target_cum_return ≤ 1000.0
- 可行时返回长度 L 为 [1, n] 的整数,否则返回 -1
- 当 `target_cum_return ≤ 0` 且任意单日收益 ≥ target 时,答案为 1
样例
Case 1 · single-day window already meets target
输入: [[0.05,-0.02,0.03,0.04,-0.01],0.04]
期望: 1
第 0 天的收益就已达到 0.05 ≥ 0.04,所以最短窗口长度 L=1。
Case 2 · multi-day window required to accumulate target
输入: [[0.01,0.01,0.01,0.01,0.01],0.025]
期望: 3
单日 0.01 < 0.025,两日 0.02 < 0.025,三日 0.03 ≥ 0.025,所以 L=3 是最短。
Case 3 · target unreachable
输入: [[0.01,0.02,0.03],1]
期望: -1
所有日累计 0.06 < 1.0,整段 6% 远不够 100%,返回 -1。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · single-day window already meets target
输入: [[0.05,-0.02,0.03,0.04,-0.01],0.04]
期望: 1
第 0 天的收益就已达到 0.05 ≥ 0.04,所以最短窗口长度 L=1。
Case 2 · multi-day window required to accumulate target
输入: [[0.01,0.01,0.01,0.01,0.01],0.025]
期望: 3
单日 0.01 < 0.025,两日 0.02 < 0.025,三日 0.03 ≥ 0.025,所以 L=3 是最短。
Case 3 · target unreachable
输入: [[0.01,0.02,0.03],1]
期望: -1
所有日累计 0.06 < 1.0,整段 6% 远不够 100%,返回 -1。