← 返回编程题库
coding-shortest-window-cum-return中等免费版2000ms未尝试

达到累计收益目标的最短窗口

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

示例 1solution([0.05, -0.02, 0.03, 0.04, -0.01], 0.04) 返回 1。第 0 天单日收益 0.05 ≥ 0.04,长度 1 的窗口已达标。示例 2solution([0.01, 0.01, 0.01, 0.01, 0.01], 0.025) 返回 3。单日 0.01 不够,两日最大 0.02 还是不够,三日 0.03 ≥ 0.025,所以最短窗口长度为 3。示例 3solution([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 可见样例;服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。

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。