连续的子数组和,并拓展为求方案数问题

简介: 连续的子数组和,并拓展为求方案数问题

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的 523. 连续的子数组和 ,难度为 中等


Tag : 「前缀和」


给你一个整数数组 nums 和一个整数 k ,编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组:


  • 子数组大小 至少为 2 ,且
  • 子数组元素总和为 k 的倍数。


如果存在,返回 true ;否则,返回 false 。


如果存在一个整数 n ,令整数 x 符合 x = n * k ,则称 x 是 k 的一个倍数。


示例 1:


输入:nums = [23,2,4,6,7], k = 6
输出:true
解释:[2,4] 是一个大小为 2 的子数组,并且和为 6 。
复制代码


示例 2:


输入:nums = [23,2,6,4,7], k = 6
输出:true
解释:[23, 2, 6, 4, 7] 是大小为 5 的子数组,并且和为 42 。 
42 是 6 的倍数,因为 42 = 7 * 6 且 7 是一个整数。
复制代码


示例 3:


输入:nums = [23,2,6,4,7], k = 13
输出:false
复制代码


提示:


  • 1 <= nums.length <= 10^5105
  • 0 <= nums[i] <= 10^9109
  • 0 <= sum(nums[i]) <= 2^{31}231 - 1
  • 1 <= k <= 2^{31}231 - 1


基本分析



这是一道很经典的前缀和题目,类似的原题也在蓝桥杯出现过,坐标在 K 倍区间

本题与那道题不同在于:


  • [K 倍区间] 需要求得所有符合条件的区间数量;本题需要判断是否存在。
  • [K 倍区间] 序列全是正整数,不需要考虑 00 值问题;本题需要考虑 00 值问题。


数据范围为 10^4104,因此无论是纯朴素的做法 (O(n^3)O(n3))还是简单使用前缀和优化的做法 (O(n^2)O(n2)) 都不能满足要求。


我们需要从 kk 的倍数作为切入点来做。


预处理前缀和数组 sumsum,方便快速求得某一段区间的和。然后假定 [i, j][i,j] 是我们的目标区间,那么有:


sum[j] - sum[i - 1] = n * ksum[j]sum[i1]=nk


经过简单的变形可得:


\frac{sum[j]}{k} - \frac{sum[i - 1]}{k} = nksum[j]ksum[i1]=n


要使得两者除 kk 相减为整数,需要满足 sum[j]sum[j]sum[i - 1]sum[i1]kk 取余相同。


也就是说,我们只需要枚举右端点 jj,然后在枚举右端点 jj 的时候检查之前是否出现过左端点 ii,使得 sum[j]sum[j]sum[i - 1]sum[i1]kk 取余相同。


前缀和 + HashSet



具体的,使用 HashSet 来保存出现过的值。


让循环从 22 开始枚举右端点(根据题目要求,子数组长度至少为 22),每次将符合长度要求的位置的取余结果存入 HashSet


如果枚举某个右端点 jj 时发现存在某个左端点 ii 符合要求,则返回 True


代码:


class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int n = nums.length;
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
        Set<Integer> set = new HashSet<>();
        for (int i = 2; i <= n; i++) {
            set.add(sum[i - 2] % k);
            if (set.contains(sum[i] % k)) return true;
        }
        return false;
    }
}
复制代码


  • 时间复杂度:O(n)O(n)
  • 空间复杂度:O(n)O(n)


拓展(求方案数)



蓝桥杯官网登录经常性罢工,我登录十几次都没登录上去,这里直接截图了 [K 倍区间] 的题目给大家。


网络异常,图片无法展示
|


写了代码,但很可惜没 OJ 可以测试 🤣


比较简单,应该没啥问题,可以直接参考 🤣


代码:


import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        long[] s  = new long[n + 1];
        for (int i = 1; i <= n; i++) s[i] = s[i - 1] + sc.nextLong();
        long ans = 0;
        Map<Long, Integer> map = new HashMap<>();
        map.put(0L, 1);
        for (int i = 1 ; i <= n; i++) {
            long u = s[i] % k;
            if (map.containsKey(u)) ans += map.get(u);
            map.put(u, map.getOrDefault(u, 0) + 1);
        }
        System.out.println(ans);
    }
}
复制代码


  • 时间复杂度:O(n)O(n)
  • 空间复杂度:O(n)O(n)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.523 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
存储 监控 算法
ClickHouse源码分析-压缩算法大揭秘
ClickHouse在近年来增加了很多压缩算法,最主要的改进还是为了更好的适应时序场景,提高压缩率,节省存储空间。本期就给大家带来ClickHouse的压缩算法介绍。
5676 0
ClickHouse源码分析-压缩算法大揭秘
|
开发工具
推荐几款typora替代品
MarkText Typedown Atom
|
存储 监控 数据可视化
SLS 虽然不是直接使用 OSS 作为底层存储,但它凭借自身独特的存储架构和功能,为用户提供了一种专业、高效的日志服务解决方案。
【9月更文挑战第2天】SLS 虽然不是直接使用 OSS 作为底层存储,但它凭借自身独特的存储架构和功能,为用户提供了一种专业、高效的日志服务解决方案。
423 9
|
11月前
|
开发者 异构计算
现在,一行命令使用Ollama运行任意魔搭GGUF模型
为了让开发者更方便地把这些模型用起来,社区最近支持了Ollama框架和ModelScope平台的链接,通过简单的 ollama run命令,就能直接加载运行ModelScope模型库上的GGUF模型。
|
人工智能
|
12月前
|
存储 SQL 关系型数据库
mysql中主键索引和联合索引的原理与区别
本文详细介绍了MySQL中的主键索引和联合索引原理及其区别。主键索引按主键值排序,叶节点仅存储数据区,而索引页则存储索引和指向数据域的指针。联合索引由多个字段组成,遵循最左前缀原则,可提高查询效率。文章还探讨了索引扫描原理、索引失效情况及设计原则,并对比了InnoDB与MyISAM存储引擎中聚簇索引和非聚簇索引的特点。对于优化MySQL性能具有参考价值。
|
存储 JavaScript 前端开发
使用JavaScript的indexOf方法
使用JavaScript的indexOf方法
|
SQL 存储 测试技术
SQL Server 查询超时问题排查
【8月更文挑战第14天】遇到SQL Server查询超时,先检查查询复杂度与索引使用;审视服务器CPU、内存及磁盘I/O负载;审查SQL Server配置与超时设置;检测锁和阻塞状况;最后审查应用代码与网络环境。每步定位问题根源,针对性优化以提升查询效率。务必先行备份并在测试环境验证改动。
906 0
|
移动开发 监控
表格中有WKWebView底部有空白问题及解决方案优缺点
表格中有WKWebView底部有空白问题及解决方案优缺点
182 0
|
关系型数据库 MySQL 数据安全/隐私保护
Navicat连接mysql8报错解决:1251- Client does not support authentication protocol requested by server
Navicat连接mysql8报错解决:1251- Client does not support authentication protocol requested by server
3458 0