P3201. 最长和为目标值的子序列

解题思路

本题一眼滑窗，直接考虑滑窗三问三答。

滑窗三问

• Q1：对于每一个右指针 right 所指的元素 num，做什么操作？
• Q2：什么时候要令左指针 left 右移？left 对应的元素做什么操作？while 中的循环不变量是什么？
• Q3：什么时候进行 ans 的更新？

滑窗三答

• A1：将 num 加入窗口和变量 win_sum 中进行计算。
• A2：当窗口和变量 win_sum 的大小超过了目标和 target，减去 left 所指的元素 left_num，同时 left 右移，直到 win_sum 小于等于目标和 target。
• A3：当 win_sum 等于目标和 target 时，此时窗口大小为 right - left + 1，更新 ans = max(ans, right - left + 1)。直接在 left 右移之后进行答案更新即可，因为此时 right 对应了以 right 为右边界，且区间和不大于 target 的区间 [left, right]。

思路展开 代码里维护三个量：left 是窗口左边界，right 是当前遍历到的右边界，win_sum 是窗口 [left, right] 内所有元素之和。right 每前进一步，先把新元素 num 累加进 win_sum；如果加完后 win_sum 超过了目标值 target，就进入 while 循环，不断把 nums[left] 从和中减掉并把 left 右移，直到窗口和重新不超过 target 为止。这个收缩之所以可行，关键在于题目保证序列全为正整数：窗口每收缩一格，win_sum 严格变小，每扩张一格，win_sum 严格变大，和随边界移动是单调的，所以以 right 结尾、和不超过 target 的最长窗口是唯一确定的，不会漏解。收缩结束后若 win_sum 恰好等于 target，说明当前窗口 [left, right] 就是一个以 right 为右端点、和为 target 的最长连续子序列，用 right - left + 1 更新答案 ans 的最大值。ans 初始化为 -1，若全程没有任何窗口的和恰好等于 target，就按题目要求输出 -1。

复杂度分析 设序列长度为 n。right 遍历全部元素一次，left 只单调右移、累计移动不超过 n 步，每个元素至多进窗一次、出窗一次，因此滑窗整体是 O(n) 时间。除读入的数组本身外，只用了 win_sum、left、ans 三个变量，额外空间复杂度 O(1)。