给定观测数据序列 x1,x2,…,xN 和目标值 T,要求找到一个连续子序列使其元素和等于长度乘以 T,并求出满足条件的最长长度。
可以考虑前缀和的做法来解此题。要求连续子序列元素和等于长度乘以 T,让每个数 xi′=xi−T,那么如果一段连续子序列满足条件,则这一段的和为 0。∑xi′=∑xi−T×length=0。
扩展开来,如果前缀和中出现某两个位置的值相等,那么根据前缀和的定义,他们间的这一段的和为 0,那么这一段的长度就是备选答案之一。
所以我们需要使用哈希来存储前缀和中每个数第一次出现的位置,当其又一次出现时,就可以计算长度作为备选答案。
小 L 获得了一组长度为 N 的观测数据 x1,x2,…,xN。他想从中截取一段连续的子序列,使得该子序列中所有元素之和恰好等于子序列长度乘以一个给定的目标值 T。换句话说,对于区间 [L,R],需要满足 ∑i=LRxi=(R−L+1)imesT。
请你计算满足条件的最长连续子序列的长度。如果不存在这样的区间,则输出 −1。
数据范围:N 不超过 105,所有 xi 及 T 均为正整数且不超过 109。
第一行包含两个正整数 N 和 T。 第二行包含 N 个正整数 x1,x2,…,xN,表示观测数据。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.