azl397985856 commented 2 months ago

1590. 使数组和能被 P 整除

入选理由

暂无

题目地址

https://leetcode.cn/problems/make-sum-divisible-by-p/

前置知识

哈希表
同余定理及简单推导

前缀和

题目描述


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

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

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

示例 1：

输入：nums = [3,1,4,2], p = 6 输出：1 解释：nums 中元素和为 10，不能被 p 整除。我们可以移除子数组 [4] ，剩余元素的和为 6 。示例 2：

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

输入：nums = [1,2,3], p = 3 输出：0 解释：和恰好为 6 ，已经能被 3 整除了。所以我们不需要移除任何元素。示例 4：

输入：nums = [1,2,3], p = 7 输出：-1 解释：没有任何方案使得移除子数组后剩余元素的和被 7 整除。示例 5：

输入：nums = [1000000000,1000000000,1000000000], p = 3 输出：0

提示：

1 <= nums.length <= 105 1 <= nums[i] <= 109 1 <= p <= 109

Martina001 commented 2 months ago

 public int minSubarray(int[] nums, int p) {
            // 这道题一看就是要用前缀和S[]
            // 下一步的重点在于推导取余公式：
            // (A-B)%p=0当A和B都是非负数的时候相当于A%p = B%p； 当A<0 B>=0时 相当于A%p +p = B%p;两种情况合起来：(A%p +p)%p =B%p
            // 设x为所有元素和
            // 题目要求是找 （x%p -( s[i]%p -s[j]%p)）%p=0，其中i>=j
            // 取模公式为 （X - SI+SJ)%p ==0 即 (SJ -(SI-X))%p = 0 套入取余公式，即 SJ%p = ((SI-X)%p+p)%p
            // 也就是说 如果遍历到ii的时候，如果之前存在索引jj 其前缀和为(S[ii]-X)%p+p的，那么[jj,ii)就是题目所说去除的子数组
            int n = nums.length, ans = n;
            int s[] = new int[n + 1];
            for (int i = 0; i < n; ++i){
                // 前缀和直接取余
                s[i + 1] = (s[i] + nums[i]) % p;
            }
            int x = s[n];
            if (x == 0) return 0;

            // map中key存储前缀和 value为索引
            HashMap<Integer,Integer> last = new HashMap<Integer, Integer>();
            for (int i = 0; i <= n; ++i) {
                last.put(s[i], i);
                // 如果不存在，-n 可以保证 i-j >= n
                int j = last.getOrDefault((s[i] - x + p) % p, -n);
                ans = Math.min(ans, i - j);
            }
            return ans < n ? ans : -1;
        }

使用了hashMap 所以只需遍历一次，时间复杂度On 空间复杂度为On 也可以直接一次遍历计算前缀和的同时计算ans

zhiyuanpeng commented 2 months ago

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        s = sum(nums) % p
        if s == 0:
            return 0

        cum_sum = 0
        d = {0: -1}
        result = len(nums)
        for j, elem in enumerate(nums):
            cum_sum = (cum_sum + elem) % p
            i = d.get((cum_sum - s) % p)
            if i is not None:
                result = min(result, j - i)
            d[cum_sum] = j

        if result == len(nums):
            return -1
        return result

CathyShang commented 2 months ago

哈希表
同余定理

前缀和

class Solution {
public:
int minSubarray(vector<int>& nums, int p) {
    // 计算nums整体的p的模
    int total_m = 0;
    for(auto num:nums){
        total_m = (total_m+num)%p;
    }
    if(total_m==0){
        return 0;
    }
    // 子数组
    unordered_map<int, int> hash_idx;
    int num_m = 0;
    int res = nums.size();
    for(int i=0; i<nums.size();i++){
        hash_idx[num_m] = i;
        num_m = (num_m + nums[i]) %p;
        if(hash_idx.count((num_m-total_m+p)%p)>0){
            res = min(res, i - hash_idx[(num_m-total_m+p)%p]+1);
        }
    }
    return res==nums.size()?-1:res;

}
};

时间 $O(N)$
空间 $O(N)$

wwz223 commented 2 months ago

/**
 * @param {number[]} nums
 * @param {number} p
 * @return {number}
 */
var minSubarray = function (nums, p) {
    let x = 0
    for (const num of nums) {
        x = (x + num) % p
    }
    if (x === 0) {
        return 0
    }
    const index = new Map()
    let y = 0; res = nums.length
    for (let i = 0; i < nums.length; i++) {
        index.set(y, i)
        y = (y + nums[i]) % p
        if (index.has((y - x + p) % p)) {
            res = Math.min(res, i - index.get((y - x + p) % p) + 1)
        }
    }
    return res === nums.length ? -1 : res
};

xil324 commented 2 months ago

```
def minSubarray(self, nums, p):
    """
    :type nums: List[int]
    :type p: int
    :rtype: int
    """
    remainder = sum(nums) % p
    if remainder == 0:
        return 0
    index_map = {0: -1}
    min_len = len(nums)
    pre_sum = 0
    for i in range(len(nums)):
        pre_sum += nums[i]
        curr_mod = pre_sum % p
        need = (curr_mod - remainder) % p
        if need in index_map:
            min_len = min(min_len, i - index_map[need])
        index_map[curr_mod] = i

    return -1 if min_len == len(nums) else min_len
 ```

Dtjk commented 2 months ago

class Solution { public: int subarraysDivByK(vector& nums, int k) { int ans = 0, n = nums.size() + 1; vector sum(n, 0); unordered_map<int, int> mp; for (int i = 1; i < n; i++) { sum[i] = sum[i - 1] + nums[i - 1]; int mod = (sum[i] % k + k) % k; mp[mod]++; }

    for (auto &[k, v] : mp) {
        if (!k) ans += v;
        ans += v * (v - 1) / 2;
    }

    return ans;
}

};

GReyQT commented 2 months ago

class Solution { public: int minSubarray(vector& nums, int p) { unordered_map<int, int> map; int deal = 0; long sum = 0; for (int i = 0; i < nums.size(); ++i) { deal = (deal + nums[i]) % p; sum += nums[i]; map[nums[i]]++; }

if (sum < p) { return -1; }

if(deal == 0) { return 0; } int ret = minKeyCount(map, deal);

return ret; }

int minKeyCount(unordered_map<int, int>& hashTable, int target) { if(hashTable.size()==1) { if(hashTable.find(target)!= hashTable.end()) { return 1; } else { return -1; } }

vector dp(target + 1, INT_MAX); dp[0] = 0;

for (const auto& kv : hashTable) { int key = kv.first; int value = kv.second;

for (int i = key; i <= target; ++i) { if (dp[i - key] != INT_MAX) { dp[i] = min(dp[i], dp[i - key] + value); } } }

return dp[target] == INT_MAX ? -1 : dp[target]; } }; 动态规划，但是还有问题。。

leetcode-pp / 91alg-13-daily-check

【Day 24 】2024-05-01 - 1590. 使数组和能被 P 整除 #25

1590. 使数组和能被 P 整除

入选理由

题目地址

前置知识

题目描述