连续的子数组和

Category	Difficulty	Likes	Dislikes
algorithms	Medium (28.56%)	526	-

Tags

math | dynamic-programming

Companies

facebook

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

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

如果存在，返回 true ；否则，返回 false 。

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

1 <= nums.length <= 105
0 <= nums[i] <= 109
0 <= sum(nums[i]) <= 231 - 1
1 <= k <= 231 - 1

Discussion | Solution

解法

 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
struct Solution;

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 动态规划
    /// 1. 设 dp[i][j]: nums[i..=j]的连续子数组和; (j>i+1)
    /// 2. 递推关系: dp[i][j+1] = dp[i][j] + nums[j]
    /// 3. 初始条件:
    ///          dp[i][i] = nums[i];
    /// 73/99 time limit exceeded
    pub fn check_subarray_sum1(nums: Vec<i32>, k: i32) -> bool {
        let n = nums.len();
        let mut dp = vec![vec![0; n + 1]; n + 1];
        for i in 0..(n - 1) {
            dp[i][i] = nums[i];
            for j in i..(n - 1) {
                dp[i][j + 1] = dp[i][j] + nums[j + 1];
                if dp[i][j + 1] % k == 0 {
                    return true;
                }
            }
        }

        false
    }

    /// - 前缀和+hashmap
    /// 1. 前缀和 prefix_sum[i]: sum(nums[..i]);
    /// 2. 连续子数组和: sub_sum[i][j] = sum(nums[i..j]) = prefix_sum[j] - prefix[i]
    /// 3. 如果 sub_sum 为 k 的倍数, 则 prefix_sum[j] % k == prefix_sum[i] % k;
    /// 4. 使用hashmap保存 (prefix_sum %k, i), 当存在同余的前缀和, 且下标差>1时, 存在k倍的子数组和;
    pub fn check_subarray_sum(nums: Vec<i32>, k: i32) -> bool {
        use std::collections::HashMap;
        let mut prefix_sum = 0;
        let mut map = HashMap::new();
        map.insert(0, -1);
        for (i, &n) in nums.iter().enumerate() {
            prefix_sum += n;
            let pre_i = *map.entry(prefix_sum % k).or_insert(i as i32);
            if (i as i32) - pre_i > 1 {
                return true;
            }
        }

        false
    }
}
// @lc code=end

连续的子数组和

连续的子数组和

解法

相关文章：