[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 条评论
登录 后参与评论

相关文章

来自专栏aCloudDeveloper

算法导论第十八章 B树

一、高级数据结构   本章以后到第21章(并查集)隶属于高级数据结构的内容。前面还留了两章:贪心算法和摊还分析,打算后面再来补充。之前的章节讨论的支持动态数据集...

1916
来自专栏King_3的技术专栏

leetcode-581-Shortest Unsorted Continuous Subarray

945
来自专栏LeetCode

LeetCode 897. Increasing Order Search Tree

题目大意:将一个BST,转化为一个只有右孩子的树,并且,这个树从根节点到叶子节点是从小到大排列的。

610
来自专栏King_3的技术专栏

leetcode-415-Add Strings

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

2017 Multi-University Training Contest - Team 1 1006&&HDU 6038 Function【DFS+数论】

Function Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K...

2715
来自专栏desperate633

LintCode 最长上升连续子序列题目样例分析1(普通解法)分析2(使用队列)

给定一个整数数组(下标从 0 到 n-1, n 表示整个数组的规模),请找出该数组中的最长上升连续子序列。(最长上升连续子序列可以定义为从右到左或从左到右的序列...

642
来自专栏desperate633

LintCode 数组剔除元素后的乘积题目代码

定义B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1], 计算B的时候请不要使用除法。

511
来自专栏King_3的技术专栏

leetcode-697-Degree of an Array

2174
来自专栏漫漫深度学习路

tensorflow学习笔记(四十五):sess.run(tf.global_variables_initializer()) 做了什么?

当我们训练自己的神经网络的时候,无一例外的就是都会加上一句 sess.run(tf.global_variables_initializer()) ,这行代码的...

2146
来自专栏LeetCode

LeetCode 169. Majority Element

思路:数组中有一个数字的出现次数超过一半,也就是说这个数字的出现次数比其他的所有的数字的出现次数之和还要多。因此我们可以考虑遍历数组的时候保存两个值,一个是数组...

331

扫码关注云+社区