1. 代码段小站首页
  2. 算法

leetcode974-和可被K整除的子数组

彭晨涛 • • 算法 • 阅读 17

原题

给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。

示例:

输入： A = [4,5,0,-2,-3,1], K = 5
输出： 7
解释：
有 7 个子数组满足其元素之和可被 K = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

提示：

  1. 1 <= A.length <= 30000
  2. -10000 <= A[i] <= 10000
  3. 2 <= K <= 10000

解法

思想

看到连续的子数组的和就要想到前缀和

代码

class Solution {
    public int subarraysDivByK(int[] A, int K) {
        int[] remainder = new int[K];
        remainder[0] = 1;
        int sum = 0;
        int count = 0;
        for(int i = 0;i<A.length;i++){
            sum += A[i];
            int remain = sum%K;
            if(remain<0) remain += K;
            count += remainder[remain];
            remainder[remain]++;
        }
        return count;
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode974-%e5%92%8c%e5%8f%af%e8%a2%abk%e6%95%b4%e9%99%a4%e7%9a%84%e5%ad%90%e6%95%b0%e7%bb%84/

赞 (0)
彭晨涛彭晨涛管理者
0 0
上一篇 2020年5月26日 22:12
下一篇 2020年5月27日 21:43

相关推荐

  • leetcode63-不同路径II 算法

    leetcode63-不同路径II

    原题 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Fi...

    彭晨涛 彭晨涛
    2020年2月22日
    0120

  • leetcode80-删除排序数组中的重复项II

    原题 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外...

    彭晨涛 彭晨涛
    算法 2020年5月26日
    0120
  • leetcode498-对角线遍历 算法

    leetcode498-对角线遍历

    这是一个Z字形编排问题，JEPG的编码过程中也会用到。 原题 给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下...

    彭晨涛 彭晨涛
    2019年11月14日
    0110

  • leetcode34--在排序数组中查找元素的第一个和最后一个位置

    原题 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 你的算法时间复杂度必须是 O(log n) 级别。 如果数...

    彭晨涛 彭晨涛
    算法 2020年1月3日
    0140

  • leetcode1014-最佳观光组合

    原题 给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。 一对景点（i < j）组成的观光组合的得分为（A[i]...

    彭晨涛 彭晨涛
    算法 2020年6月17日
    01660

  • leetcode14-最长公共前缀

    原题 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 “”。 示例 1: 输入: [“flower”,”flow”,”flight”] 输出: “...

    彭晨涛 彭晨涛
    算法 2019年11月18日
    090
  • leetcode206-反转链表 算法

    leetcode206-反转链表

    原题 反转一个单链表。 示例： 输入： 1->2->3->4->5->NULL 输出： 5->4->3->2->1->NULL 进阶： 你可以迭代或递归地反转链表。你能否用两种方法...

    彭晨涛 彭晨涛
    2019年12月16日
    0140

  • leetcode385-迷你语法分析器

    原题 给定一个用字符串表示的整数的嵌套列表，实现一个解析它的语法分析器。 列表中的每个元素只可能是整数或整数嵌套列表 提示： 你可以假定这些字符串都是格式良好的： 字符串非空 字符...

    彭晨涛 彭晨涛
    算法 2020年1月28日
    02170

  • leetcode701-二叉搜索树中的插入操作

    原题 给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。 注意，可能存在多种有效的插入方式，只...

    彭晨涛 彭晨涛
    算法 2020年1月16日
    0100

  • leetcode8-字符串转换整数 (atoi)

    原题 请你来实现一个 atoi 函数，使其能将字符串转换成整数。 首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下： 如果第一个...

    彭晨涛 彭晨涛
    算法 2020年4月3日
    0270

发表回复

登录后才能评论