思路:前缀和
给定观测数据序列 x1,x2,…,xN 和目标值 T,要求找到一个连续子序列使其元素和等于长度乘以 T,并求出满足条件的最长长度。
可以考虑前缀和的做法来解此题。要求连续子序列元素和等于长度乘以 T,让每个数 xi′=xi−T,那么如果一段连续子序列满足条件,则这一段的和为 0。∑xi′=∑xi−T×length=0。
扩展开来,如果前缀和中出现某两个位置的值相等,那么根据前缀和的定义,他们间的这一段的和为 0,那么这一段的长度就是备选答案之一。
所以我们需要使用哈希来存储前缀和中每个数第一次出现的位置,当其又一次出现时,就可以计算长度作为备选答案。