「力扣」第 523 题:连续的子数组(中等)

liweiwei1419 ... 2022-1-6 前缀和
  • 前缀和
  • 哈希表
About 5 min

# 题目描述

给你一个整数数组 nums 和一个整数 k ,编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组:

  • 子数组大小 至少为 2 ,且
  • 子数组元素总和为 k 的倍数。

如果存在,返回 true ;否则,返回 false

如果存在一个整数 n ,令整数 x 符合 x = n * k ,则称 xk 的一个倍数。0 始终视为 k 的一个倍数。

示例 1:

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

示例 2:

输入:nums = [23,2,6,4,7], k = 6
输出:true
解释:[23, 2, 6, 4, 7] 是大小为 5 的子数组,并且和为 42 。
42 是 6 的倍数,因为 42 = 7 * 6 且 7 是一个整数。
1
2
3
4

示例 3:

输入:nums = [23,2,6,4,7], k = 13
输出:false
1
2

提示:

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9
  • 0sum(nums[i])23110 \le sum(nums[i]) \le 2^{31} - 1
  • 1k23111 \le k \le 2^{31} - 1

# 思路分析

说明:本题解修改自原始的官方题解,现在的官方题解已经被官方题解团队修改过。

概述

  • 这道问题我们使用三种方法,层层递进介绍了这个问题的解法,基本的思路是 空间换时间
  • 如果空间使用恰当,可以减少遍历的次数;
  • 这道问题的方法二和方法三都很有代表性,大家需要仔细体会。

# 方法一:暴力解法(超时)

考虑所有长度 大于等于 22 的连续子数组,将各个子数组遍历一遍求和,并判断和是否是给定整数 kk 的倍数。

参考代码 1

public class Solution {

    public boolean checkSubarraySum(int[] nums, int k) {
        int len = nums.length;
        for (int left = 0; left < len - 1; left++) {
            for (int right = left + 1; right < len; right++) {
                int sum = 0;
                for (int i = left; i <= right; i++) {
                    sum += nums[i];
                }
                if (sum == k || (k != 0 && sum % k == 0)) {
                    return true;
                }
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

复杂度分析

  • 时间复杂度:O(N3)O(N^3) 。三重嵌套的 for 循环遍历数组;
  • 空间复杂度:O(1)O(1) ,只用了常数个额外变量。

# 方法 2:前缀和(超时)

基本思想:空间换时间。

  • 注意到题目中我们求连续子数组的区间和;
  • 求区间和的一个基本的技巧是:根据前缀和的差,求出区间和。

参考代码 2

public class Solution {

    public boolean checkSubarraySum(int[] nums, int k) {
        int len = nums.length;

        // preSum[i] 表示:区间 [0..i) 的前缀和
        int[] preSum = new int[len + 1];
        preSum[0] = 0;
        for (int i = 0; i < len; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }


        for (int left = 0; left < len - 1; left++) {
            for (int right = left + 1; right < len; right++) {
                int sum = preSum[right + 1] - preSum[left];
                if (sum == k || (k != 0 && sum % k == 0)) {
                    return true;
                }
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

复杂度分析

  • 时间复杂度: O(n2)O(n^2) 。为了考虑每一个子数组,我们需要一个 2 重嵌套的循环。
  • 空间复杂度: O(n)O(n) 。 使用了长度为 nnsumsum 数组。

事实上,当前问题是一个计数问题,根据求解 1. 两数之和 的经验,我们可以在遍历的过程当中记录已经出现的信息,这样就可以通过一次遍历完成计算。已经遍历过的信息就需要记录下来,我们使用 哈希表


# 方法 3:前缀与哈希表

使用哈希表保存到下标 ii 个止的元素的和,并且 对这个前缀和除以 kk 取余数(请大家思考这是为什么?)

原因如下:遍历输入数组,记录到当前位置为止的 sum%ksum\%k,一旦我们找到新的 sum%ksum\%k 的值(即在哈希表中没有这个值),我们就 往哈希表中插入一条记录 key:sum % k,value:i

假设第 ii 个位置的 sumsum % k 的值为 remrem。如果以 ii 为左端点的任何子数组的和是 kk 的倍数,假设该位置为 jj ,那么哈希表中第 jj 个元素保存的值为 (rem+nk)%k(rem + n*k)\%k ,其中 n>0n > 0 整数。发现 (rem+nk)%k=rem(rem + n*k)\%k = rem ,也就是跟第 ii 个元素保存到哈希表 中的值相同。

基于这一观察,可以得出结论:

无论何时,只要 sum%ksum\%k 的值已经被放入哈希表,代表着有两个下标 iijj ,它们之间元素的和是 kk 的整数倍。因此只要哈希表中有相同的 sum%ksum\%k ,就可以直接返回 \teat{True}

下面的幻灯片描述了数组 nums = [2, 5, 33, 6, 7, 25, 15]k = 13 的求解过程。

import java.util.HashMap;
import java.util.Map;

public class Solution {

    public boolean checkSubarraySum(int[] nums, int k) {
        int sum = 0;

        // key:区间 [0..i] 里所有元素的和 % k
        // value:下标 i
        Map<Integer, Integer> map = new HashMap<>();
        // 理解初始化的意义
        map.put(0, -1);
        int len = nums.length;
        for (int i = 0; i < len; 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

复杂度分析

  • 时间复杂度:O(N)O(N),仅需要遍历输入数组一遍;
  • 空间复杂度:O(min(n,k))O(min(n,k))。哈希表最多包含 min(n,k)min(n,k) 个不同的元素。
Last update: January 14, 2022 00:19
Contributors: liweiwei1419