LEETCODE 523. Continuous Subarray Sum 解题思路分析

题目大意:

连续的子数组和

给定一个包含 非负数 的数组和一个目标 整数 k,编写一个函数来判断该数组是否含有连续的子数组,其大小至少为 2,且总和为 k 的倍数,即总和为 n*k,其中 n 也是一个整数。

示例 1:

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

示例 2:

输入:[23,2,6,4,7], k = 6
输出:True
解释:[23,2,6,4,7]是大小为 5 的子数组,并且和为 42。

说明:

  • 数组的长度不会超过 10,000 。
  • 你可以认为所有数字总和在 32 位有符号整数范围内。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=523

解题思路分析:

本题前缀和数组加暴力解是可行的,但本文我们力求最优解,因此,暴力解法简单带过。

解法一:前缀和加暴力遍历每个子数组。

  1. 先计算出前缀和数组。推导公式如下:
    • presum[0]=nums[0]
    • presum[i]=presum[i-1]+nums[i] (i>0)
  2. 两层循环,遍历每一个子数组,当前子数组区间[i,j]和的公式如下。查看该和是否能被k整除
    • presum[j] – presum[i] + nums[i]

实现代码:

public class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int[] sum = new int[nums.length];
        sum[0] = nums[0];
        for (int i = 1; i < nums.length; i++)
            sum[i] = sum[i - 1] + nums[i];
        for (int start = 0; start < nums.length - 1; start++) {
            for (int end = start + 1; end < nums.length; end++) {
                int summ = sum[end] - sum[start] + nums[start];
                if (summ == k || (k != 0 && summ % k == 0))
                    return true;
            }
        }
        return false;
    }
}

解法二:HashMap。O(n)解法

本解法我们依旧需要利用到前缀和数组,但是数组中存的不是和,而是前缀和与k的余数。

试想,如果一个子数组区间[i, j]之和与k的余数为0,也就是说:

(presum[j]-presum[i]+nums[i]) mod k == 0.

我们可将上述公式推导为:

(presum[j]-presum[i-1]) mod k == 0.

进而得到:

presum[j] mod k == presum[i-1] mod k

因此可得出结论,当前缀和数组中出现相同数值时(注意数组中存放的是前缀和与k的余数),我们可以推导出当前存在一个子数组之和可以被k整除。解题时,我们另外使用一个HashMap,记录已经出现过的前缀和(前缀和与k的余数)。另外注意对数字0的处理,详见代码。

实现代码:

public boolean checkSubarraySum(int[] nums, int k) {
    int sum = 0;
    HashMap <Integer, Integer> map = new HashMap<>();
    map.put(0, -1);
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (k != 0) sum = sum % k;
        if (map.containsKey(sum)) {
            if (i - map.get(sum) > 1) return true;
        }else map.put(sum, i);
    }
    return false;
}

本题解法执行时间为2ms。

Runtime: 2 ms, faster than 99.79% of Java online submissions for Continuous Subarray Sum.

Memory Usage: 52.7 MB, less than 5.06% of Java online submissions for Continuous Subarray Sum.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-523-continuous-subarray-sum-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。