政府门户网站制度建设淘宝代运营公司

一、题目

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/make-sum-divisible-by-p/description/

二、C++解法

我的思路及代码

我的方法时间复杂度太高，导致不能通过测试用例
采用前缀和的思路，然后从头开始用不同的窗口大小对数组进行遍历，窗口内的元素即为被删除的元素，直到最后剩下的数组元素和可以被整除返回当前的窗口大小，否则返回 -1。由于本题目只需要判断是否可以被整除，所以在前缀和中我们可以简化存储的数据，每次可以存储取余后的数据。

class Solution {
public:int minSubarray(vector<int>& nums, int p) {int size = nums.size();int prefixSum[size+1];int ans=1;prefixSum[0] = 0;for(int i=1;i<nums.size()+1;i++){prefixSum[i] = (prefixSum[i-1]+nums[i-1])%p;}if(prefixSum[size]%p==0)return 0;while(ans<size+1){for(int j=ans;j<size+1;j++){if((prefixSum[size]-(prefixSum[j]-prefixSum[j-ans]))%p==0)return ans;}ans++;}return -1;}
};

• 时间复杂度：O(n²)，其中 n 是数组 nums 的长度
• 空间复杂度：O(n)，数组需要 O(n) 的空间

官方参考代码

前缀和+哈希表

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。遍历数组 nums 需要 O(n) 的时间
• 空间复杂度：O(n)，保存哈希表需要 O(n) 的空间