美团2018校招编程—K的倍数

简单描述：输入为三行，第一行为第二行的数组的列数，第二行表示一个数组，第三行数字为K。需要求出数组子串的长度，要求这个子串能够整除K，并且是所有满足这样要求的子串中最长的一串。

以下是输入： - N–数组元素的数量 0<N<10 5   - P i   为每个元素的数值，有N个 - K，要求能被整除的数。

解题思路

利用滑动窗口的原理，窗口最大长度为 N  ,判断窗口内子串和是否为K 的整数倍，不是则向右移动窗口，直至窗口边界越过数组的边界。当窗口边界越过数组边界时，减小窗口长度，重新从数组起点移动窗口，直到找到满足要求的窗口，跳出循环，输出窗口长度。

代码如下：

int main() { int N; int element_P; int K; vector<int> array_P; cin >> N; for (int i = 0; i < N; i++) { cin >> element_P; array_P.push_back(element_P); } cin >> K; long sumOfarray=0; for (int i = 0; i < array_P.size(); i++) { sumOfarray += array_P[i]; } int length = array_P.size(); int leftend; int rightstart; long sumOfleft; long sumOfright; while (length > 0) { leftend = 0; rightstart = length; sumOfleft = 0; sumOfright = 0; for (int i = 0; i < leftend; i++) sumOfleft += array_P[i]; for (int i = array_P.size()-1; i >=rightstart;i--) sumOfright += array_P[i]; while (rightstart < array_P.size()) { if ((sumOfarray - sumOfleft - sumOfright) % K == 0) break; else { sumOfleft += array_P[leftend]; leftend++; sumOfright -= array_P[rightstart]; rightstart++; } } if (rightstart < array_P.size()|| (sumOfarray - sumOfleft - sumOfright) % K == 0) break; length--; } cout << length; system("pause"); return 0; }