【LeetCode】连续的子数组和 Java 题解

关注

发布于: 2021 年 06 月 03 日

题目描述

给你一个整数数组 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 。
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/continuous-subarray-sum著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

这是一道中等难度的题目，含义容易理解，首先可以通过朴素解法求解。枚举所有的子数组，由于题目求解只需要子数组的和，自然而然想到了用前缀和提升效率。
前缀和是一种预计算，常见的实现代码如下：

        int[] preSum = new int[n];        preSum[0] = nums[0];        for (int i = 1; i < n; i++) {            preSum[i] = preSum[i - 1] + nums[i];        }

复制代码

AC 代码

public class DayCode {    public static void main(String[] args) {
        int[] nums1 = new int[]{23, 2, 4, 6, 6};        int k1 = 7;
        boolean ans1 = new DayCode().checkSubarraySum1(nums1, k1);        System.out.println(ans1);
        boolean ans2 = new DayCode().checkSubarraySum2(nums1, k1);        System.out.println(ans2);    }

    /**     * 时间复杂度 O(n * n)     * 空间复杂度 O(n)     *     * @param nums     * @param k     * @return     */    public boolean checkSubarraySum1(int[] nums, int k) {        int n = nums.length;        if (n < 2) {            return false;        }        int[] preSum = new int[n + 1];        for (int i = 0; i < n; i++) {            preSum[i + 1] = preSum[i] + nums[i];        }        for (int i = 0; i < n; i++) {            for (int j = i + 2; j < n; j++) {                if ((preSum[j] - preSum[i]) % k == 0) {                    return true;                }            }        }        return false;    }

    /**     * 时间复杂度 O(n)     * 空间复杂度 O(n)     *     * @param nums     * @param k     * @return     */    public boolean checkSubarraySum2(int[] nums, int k) {        int n = nums.length;        if (n < 2) {            return false;        }
        Map<Integer, Integer> map = new HashMap<>();        map.put(0, -1);        int preSum = 0;        int remainder = 0;        for (int i = 0; i < n; i++) {            preSum += nums[i];            remainder = preSum % k;            if (map.containsKey(remainder)) {                if (i - map.get(remainder) >= 2) {                    return true;                }            } else {                map.put(remainder, i);            }        }        return false;    }}

复制代码

总结

上述代码算法一的时间复杂度 O(n * n), 空间复杂度是 O (n)
上述代码算法二的时间复杂度 O(n * n), 空间复杂度是 O (n)
算法二是这个题目的最优解，这个解法来自于官方题解，采用了 hashmap, 前缀和, 同余数学思想合作解决。
这种题目是在实际考察中比较常见的，结合多个知识点，综合解决。勤加练习，可以掌握的更好！
坚持每日一题，加油！

发布于: 2021 年 06 月 03 日阅读数: 5

原文链接:【http://xie.infoq.cn/article/71ea3c7ea7d6fa1e20776ff98】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】连续的子数组和 Java 题解

题目描述

思路分析

AC 代码

总结

HQ数字卡

评论