代码编织梦想

使数组和能被 P 整除【LC1590】

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

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

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

这种只差一点的感觉 真难受

  • 思路

    假设数组总和为 s u m sum sum,删除的数组范围为 [ l e f t , r i g h t ] [left,right] [left,right],那么可以通过前缀和数组计算出删除数组的和,记为 y y y,此时剩余元素之和为 s u m − y sum-y sumy,如果剩余元素之和能够整除p,那么此时满足
    ( s u m − y ) % p = 0 y = s u m % p (sum-y)\%p=0 \\y = sum \% p (sumy)%p=0y=sum%p
    通过前缀和数组可得
    p r e [ r i g h t ] − p r e [ l e f t ] = s u m % p p r e [ l e f t ] = ( p r e [ r i g h t ] − s u m ) % p pre[right]-pre[left] = sum \% p \\pre[left] =(pre[right]-sum) \% p pre[right]pre[left]=sum%ppre[left]=(pre[right]sum)%p
    因此我们可以将前缀和放入哈希表中,哈希表存放前缀和及其对应的下标,然后对于每个right,查找是否有符合的left,有则更新最小长度

  • 实现

    为了防止越界,前缀和数组记录对p取余的结果

    class Solution {
        public int minSubarray(int[] nums, int p) {
            int n = nums.length, ans = n;
            var 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; // 移除空子数组(这行可以不要)
    
            var 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;
        }
    }
    
    作者:灵茶山艾府
    链接:https://leetcode.cn/problems/make-sum-divisible-by-p/solutions/2158435/tao-lu-qian-zhui-he-ha-xi-biao-pythonjav-rzl0/
    来源:力扣(LeetCode)
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
    
    • 复杂度
      • 时间复杂度: O ( n ) O(n) O(n)
      • 空间复杂度: O ( n ) O(n) O(n)
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Tikitian/article/details/129439249

sicily 题目分类-爱代码爱编程

依照自己水平挑着做→ →~~ 1. 编程入门 2. 数据结构 3. 字符串 4. 排序 5. 图遍历 6. 图算法 7. 搜索:剪枝,启发式搜索 8. 动态规划/递推 9. 分治/递归 10. 贪心 11. 模拟 12. 算术与代数 13. 组合问题 14. 数论 15. 网格,几何,计算几何 【编程入门】 PC 110101, uva 10

刷题刷题-爱代码爱编程

                     POJ推荐50题   第一类 动态规划(至少6题,2479 和 2593 必做)  2479 和 2593 1015 1042(可贪心)1141 1050 1080 1221 1260 2411(稍难)1276  第二类 搜索(至少4题)  1011 1033 1129 2049 2056 2488 

pku online judge poj流传最广的分类,acmer必备-爱代码爱编程

原文链接:http://www.cnhonkerarmy.com/forum.php?mod=viewthread&tid=2927&page=1 多版本的POJ分类 流传最广的一种分类: 初期: 一.基本算法:      (1)枚举. (poj1753,poj2965)      (2)贪心

[sicily]部分题目分类-爱代码爱编程

sicily题目分类 1. 编程入门 2. 数据结构 3. 字符串 4. 排序 5. 图遍历 6. 图算法 7. 搜索:剪枝,启发式搜索 8. 动态规划/递推 9. 分治/递归 10. 贪心 11. 模拟 12. 算术与代数 13. 组合问题 14. 数论 15. 网格,几何,计算几何 【编程入门】 PC 110101, uva 100, The

269道各路算法考试题集锦-爱代码爱编程

1 某编程大赛题(35道题,中等难度) 1、在实际的开发工作中,对于string的处理是最常见的编程任务,本题是要求程序对用户输入的string进行处理,具体要求如下: 1、每个单词的首字母变为大写。 2、将数字与字母之间用下划线隔开,使结构清晰。 3、多个空格变为1个空格。 示例:输入:you and me what cpp2005pragram 则

蓝桥杯c++ab算法辅导_violet~evergarden的博客-爱代码爱编程

文章目录 1.1 教学计划与递归92. 递归实现指数型枚举94. 递归实现排列型枚举717. 简单斐波那契95. 费解的开关 1.2 递推与递归——习题课93. 递归实现组合型枚举1209. 带分数116. 飞行

剑指offer刷题笔记整理_ml_python_get√的博客-爱代码爱编程

剑指offer刷题笔记 day102 回文链表03 I 数组中重复的是数字03II 不修改数组找出重复的数字04 二维有序数组的查找05 替换空格06 从尾到头打印链表07 根据前序和中序重新构建二叉树08 二叉树中

1590. 使数组和能被 p 整除-哈希表法_mr gao的博客-爱代码爱编程

1590. 使数组和能被 P 整除-哈希表法 给你一个正整数数组 nums,请你移除 最短 子数组(可以为 空),使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。 请你返回你需要移除的最短子数组的长度,如

[日记]leetcode算法·二十三——单调栈-爱代码爱编程

1 单调栈 单调栈和单调队列作为线性结构,通过保持一定的序列性,从而能很好地适应寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置。单调栈与单调队列的本质都是空间换时间,通过保存可能用到的所有极值,省去了过多的重

2刷第二天(leetcode977. 有序数组的平方、leetcode209. 长度最小的子数组、leetcode59. 螺旋矩阵 ii)-爱代码爱编程

一.有序数组的平方:                 题目链接:给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。 解法:                 1.本题首先的想法就是都给它平方了,然后调用sort方法,但是时间复杂度会很高。                 2.考虑双指针解

【leetcode】剑指 offer(19)-爱代码爱编程

目录 题目:剑指 Offer 36. 二叉搜索树与双向链表 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 题目:剑指 Offer 36. 二叉搜索树与双向链表 - 力扣(Leetcode) 题目的接口: /* // Definition for a Node. class Node {