题目描述

给你一个正整数长度为 $n$ 数组 $nums$，请你移除 最短 子数组（可以为 空），使得剩余元素的 和 能被 $p$ 整除。 不允许 将整个数组都移除。

请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。

子数组 定义为原数组中连续的一组元素。

输入格式

第一行两个整数 $n$ 和 $p$ ；

第二行 $n$ 个空格隔开的整数，表示数组中的元素。

输出格式

一行一个整数表示答案。

示例 1：

4 6
3 1 4 2

1

解释： nums 中元素和为 10，不能被 p 整除。我们可以移除子数组 [4] ，剩余元素的和为 6 。

示例 2：

4 9
6 3 5 2

2

解释： 我们无法移除任何一个元素使得和被 9 整除，最优方案是移除子数组 [5,2] ，剩余元素为 [6,3]，和为 9 。

示例 3：

3 3
1 2 3

0

解释： 和恰好为 6 ，已经能被 3 整除了。所以我们不需要移除任何元素。

示例  4：

3 7
1 2 3

-1

解释： 没有任何方案使得移除子数组后剩余元素的和被 7 整除。

示例 5：

3 3
1000000000 1000000000 1000000000

0

提示：

• $1 <= n <= 10^5$
• $1 <= nums[i] <= 10^9$
• $1 <= p <= 10^9$

SOURCE

1590. 使数组和能被 P 整除