求取固定方向移动收集目标硬币所需最少步数的算法优化问题

问题本质转化 #

首先可以把原问题做等价转化：你要求的收集路径本质是一段连续的房屋子数组——无论选择哪个起点、往哪个方向移动，最终收集的硬币都对应原数组里的一段连续元素，移动步数就是这段子数组的长度。因此原问题等价于：求数组中和≥目标值t的连续子数组的最小长度。

方案对比 #

原有遍历方案 #

• 时间复杂度：O(n²)，每个起点分别向左、向右遍历时，最坏情况需要走完整条数组，总操作量随n平方级增长，仅适合n极小的场景。

优化方案（滑动窗口法） #

前提：题目中房屋硬币数均为非负数，符合常规业务逻辑。

实现逻辑

利用非负数组的前缀和单调递增特性，用双指针维护滑动窗口，仅需一次遍历即可得到结果：

1. 初始化左指针left = 0、当前窗口和current_sum = 0、最小步数min_step = 正无穷
2. 右指针right从0到n-1遍历数组：
   • 将nums[right]加入current_sum
   • 只要current_sum ≥ t：
     • 更新min_step为min(min_step, right - left + 1)
     • 从current_sum中减去nums[left]，左指针右移一位
3. 遍历结束后，若min_step仍为正无穷，说明所有房屋硬币总和不足t，返回数组总长度即可，否则返回min_step

效率表现

时间复杂度为O(n)，左右指针最多各遍历数组一次，n越大相比原有方案的性能优势越明显。

示例验证

代入你给出的示例nums = [5,1,2,3,4]、t=13：
遍历过程中所有满足和≥13的连续子数组最短长度为5，和示例结果一致。

特殊场景扩展 #

如果题目允许硬币数为负数，可改用前缀和+单调队列的方案，时间复杂度仍可保持O(n)，不过常规硬币问题下滑动窗口方案已经完全够用。

内容的提问来源于stack exchange，提问作者daniel