[LeetCode] 523. Continuous Subarray Sum

【原题】 Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

Example 1:

Input: [23, 2, 4, 6, 7], k=6 Output: True Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:

Input: [23, 2, 6, 4, 7], k=6 Output: True Explanation: Because [23,2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

【解释】 给定一个数组和一个target,要求返回数组中是否存在连续子数组的和是k的倍数,要求连续子数组的元素个数大于2 【思路】

思路一、 直接从每一个元素开始,依次和其后的元素分别相加,如果为k的倍数返回true即可。O(n^2)的解法,这里略过。

思路二、 o(n^2)的方法有点low,想用求最大子数组和的滑动窗口的思想来做,但没有解出来。于是就看了solution。 需要使用一个定理:

如果x和y除以z同余,那么x-y一定可以整除z

public boolean checkSubarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(0, -1);//为了处理nums=[0,0] k=-1这样的情况
        int sum = 0;
        for (int i=0;i<nums.length;i++) {
            sum += nums[i];
            if (k != 0) sum %= k; 
            Integer prev = map.get(sum);
            if (prev != null) {
                if (i - prev > 1) return true;//若找到相同的余数,并且元素不少于两个,利用上面的定理,则返回true
            }
            else map.put(sum, i);//否则将余数和index保存至map
        }
        return false;
    }

这种题目之前没有做过确实很难想到这样的解法,具有很强的技巧性。

参考: https://discuss.leetcode.com/topic/80793/java-o-n-time-o-k-space

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PPV课数据科学社区

R与数据分析学习总结之一:R语言基本操作

? 最近开始学习R语言,把学习笔记和小伙伴们分享一下吧,欢迎一起交流 R 起源: R是S语言的一种实现。S语言是由 AT&T贝尔实验室开发的一种用来进行数据探...

4256
来自专栏mathor

逻辑代数

975

与机器学习算法有关的数据结构

可能你对经常使用的统计分类包中的功能不满足你的需求而感到不爽,或者你已经有了一个新的数据处理方法。所以,你决定改动现有封装好的算法,开始编写你自己的机器学习方法...

2337
来自专栏小樱的经验随笔

UVALive 3882 - And Then There Was One【约瑟夫问题】

题目链接:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=...

2606
来自专栏数据结构与算法

字符串hash入门

简单介绍一下字符串hash 相信大家对于hash都不陌生 hash算法广泛应用于计算机的各类领域,像什么md5,文件效验,磁力链接 等等都会用到hash算法 在...

3195
来自专栏好好学java的技术栈

“365算法每日学计划”:java语言基础题目及解答(01-05打卡)

如果有小伙伴很少接触到这种题目的话,可能会觉得有点陌生,不知道从何下手,可能一开始我们能想到“最笨”的方法,但是也觉得挺有“娱乐性”的方法。

1315
来自专栏AzMark

贝斯狸的 Python 之旅 -- 深入切片操作及原理

我首先通过 input() 函数,接收了外部输入字符串,然后通过 list 函数的切片,实现了回文数,代码真的好简洁,我自己都佩服我自己,我也不知道小组长会问...

663
来自专栏猿人谷

为什么使用抽象类?有什么好处?

最简单的说法也是最重要的理由:接口和实现分离 老是在想为什么要引用抽象类,一般类不就够用了吗。一般类里定义的方法,子类也可以覆盖,没必要定义成抽象的啊。 看了下...

1669
来自专栏人工智能头条

Python 再牛,在字符串排序上还是被 Julia 和 R 碾压

在《实例对比 Julia, R, Python,谁是狼语言?》我们简单介绍了 Julia 的背景,以及通过优化一个似然函数的参数 μ 和 σ,来对比 Julia...

733
来自专栏null的专栏

C/C++——柔性数组

1、问题来源 在博文数据结构和算法——kd树中,在构建kd树的过程中,有如下的一段代码: #define MAX_LEN 1024 typedef struc...

2734

扫码关注云+社区