DEV Community
·
1590. 使数组和可被 P 整除
💡
原文英文，约900词，阅读约需4分钟。
📝
内容提要
给定一个正整数数组`nums`，要求移除最小子数组，使剩余元素之和能被`p`整除。首先计算数组总和对`p`的余数`r`，然后使用前缀和和哈希表遍历数组，寻找满足条件的前缀和。若找到，更新最小子数组长度；若找不到，返回-1。时间复杂度为O(n)，空间复杂度为O(n)。
🎯
关键要点
- 给定一个正整数数组，要求移除最小子数组，使剩余元素之和能被p整除。
- 计算数组总和对p的余数r。
- 使用前缀和和哈希表遍历数组，寻找满足条件的前缀和。
- 若找到，更新最小子数组长度；若找不到，返回-1。
- 时间复杂度为O(n)，空间复杂度为O(n)。
- 示例1：输入[3,1,4,2]，p=6，输出1。
- 示例2：输入[6,3,5,2]，p=9，输出2。
- 示例3：输入[1,2,3]，p=3，输出0。
- 使用前缀和计算子数组和。
- 需要找到一个子数组，使得移除后剩余元素之和能被p整除。
- 使用哈希表存储每个前缀和的最后出现索引，以便快速查找。
➡️
