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

相关文章

来自专栏恰同学骚年

剑指Offer面试题:13.调整数组顺序使奇数位于偶数前面

  例如有以下一个整数数组:12345,经过调整后可以为:15342、13542、13524等等。

1016
来自专栏python学习之旅

算法笔记(八):复杂度分析(二)

#感兴趣的可以去订阅极客时间前谷歌工程师的专栏:数据结构与算法之美,个人觉得写的很不错。这里只是我自己做的一个简单的笔记

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

C/C++中连接函数strcat的应用(简单讲解)

有位学弟问到我如何将两个字符连接起来,想想java/python里面可以直接用+连接起来,可是C/C++里面有没有这么方便的做法呢?

902
来自专栏武培轩的专栏

排序算法-冒泡排序

算法简介 冒泡排序(Bubble Sort)是一种典型的交换排序算法,持续比较相邻元素,大的挪到后面,因此大的会逐步往后挪,故称之为冒泡。 算法描述 比较相邻的...

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

P3709 大爷的字符串题(50分)

题目背景 在那遥远的西南有一所学校 /*被和谐部分*/ 然后去参加该省省选虐场 然后某蒟蒻不会做,所以也出了一个字符串题: 题目描述 给你一个字符串a,每次询问...

3347
来自专栏Python小屋

妙用Python内置函数int()快速计算等比数列前n项和

本文要点在于Python内置函数int()的用法,所以计算等比数列前n项和时没有使用数学上的公式Sn=a1*(1-q^n)/(1-q)。 一般遇到这样的问题,很...

4176
来自专栏郭耀华‘s Blog

十大经典排序算法最强总结(含JAVA代码实现)

最近几天在研究排序算法,看了很多博客,发现网上有的文章中对排序算法解释的并不是很透彻,而且有很多代码都是错误的,例如有的文章中在“桶排序”算法中对每个桶进行排...

4477
来自专栏noteless

[一]基础类型概述

https://docs.oracle.com/javase/tutorial/java/nutsandbolts/datatypes.html

863
来自专栏机器学习和数学

[编程经验]Python中的Lambda,Map, Reduce小结

今天要和大家分享的是Python匿名函数(anonymous functions),也叫lambda函数。匿名函数的意思就是说这个函数没有显式的函数名,因为一般...

3265
来自专栏nnngu

算法02 七大排序之:直接选择排序和堆排序

上一篇总结了交换排序的冒泡排序和快速排序。这一篇要总结的是选择排序,选择排序分为直接选择排序和堆排序,主要从以下几点进行总结。 1、直接选择排序及算法实现 2、...

3537

扫码关注云+社区