Leetcode 523 Continuous Subarray Sum

发表于 更新于 分类于 阅读次数：

Problem

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. 42 is a mutiple of 6 and 7 and n=7.

Note:

  1. The length of the array won’t exceed 10,000.
  2. You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

Solution

基本思想

本题是一个经典的动态规划问题，此类问题的特征是，需要在穷举的可能性中找到一个最优化的解，从而求出所需问题的答案。本题的目标是找到所有和为K的连续子数组的个数。虽然本题没有直接提问一个最优解的概念，但是其实和为K的连续子数组的个数就是在穷举所有可能性后得出的并且是唯一的结果。

本题的解题思路是采用是动态规划思想，一般来讲，动态规划题目的解题思路如下：

  1. 找出最优解性质，并刻画其结构特征;
  2. 递归的定义最优值;
  3. 自底向上的方式算出最优值；
  4. 根据计算最优值时得到的信息构造最优解。

动态规划解题的前提假设是：问题的最优解包含着其自问题的最优解。此种性质称为最优子结构性质。最优子结构性质不难通过反证法证明。

递归关系的建立，是基于已有的前提最优解，所以不难在此基础上推导出递增关系。

解题思路

本题中，连续子数组的和是可以通过数组前缀和算出来的。两个长度不同的数组S[i], S[j]的前缀和相减就能计算出子数组S[(i+1)~j]的和。

数组前缀和定义：一个数组从0号元素相加到k号元素则是该数组的第k个前缀和。下文用Sum(k)表示。

假设已知长度为k的所有长度大于2的子数组后缀和中，是K的整数倍的有a(k)个，则当在k+1的情况下，a(k+1)则是a(k)+所有k的子数组后缀和中值为K的整数倍-a[k+1]的个数。

数组后缀和定义：一个数组从最后一个元素加到倒数第k的元素，是该数组的第k个后缀和。

长度为k的数组的所有子数组的后缀和计算，可以利用数组的前缀和计算出。a(k)情况下，其后缀和的集合为第k个前缀和减去第i个前缀和(0<=i<k)的数集。

为求得所有k的子数组后缀和中值为K的整数倍-a[k+1]的个数，需要求出所有k的整倍数-a[k+1]的个数。循环终止于当k的倍数大于整个序列和。

程序设计

本程序需要维护一个HashMap，每个key都是一个前缀和，value则是前缀和的子数组个数。从而在每步的计算中能够利用这个数据结构最优查找速度。

每步的运算设计思想是找到重复的子问题，从而能在一步一步地推中找到第n步的答案。每步的计算中需要找到第k后缀和中符合条件的解，也就是HashMap中key值为sum-K_multiple的value。计算公式推导如下：

1
2
3
4
5
第k后缀和中符合条件的解
    =[所有K的整倍数a[k+1]-为a[k]后缀和的]value
    =[所有K的整倍数-a[k+1]为(Sum(k)-Sum(i))]的value, i=0,1,...,k-2中某值
    =[所有K的整倍数为(Sum(k+1)-Sum(i))]的value
    =[Sum(i)中值为(Sum(k+1)-所有K的整数倍)]的value

本算法需要计算从0到n的所有子数组前缀和并进行O(1)的HashMap查找，所以最终的复杂度为O(n)。

实现技巧

边界条件考虑：

  1. 长度至少为2的子数组；

    对于存在单个数为K的整数倍的数组，单数的情况是不能统计进最终结果的，所以需要在查找匹配的情况下去检查Sum(i)是否为previous_sum。如果是且value=1就需要剔除该种情况。

  2. 非负序列

    注意，value是可以不为1的，因为非负序列是可以存在连续的0元素。

  3. K的整数倍

    K的整数倍包括负数倍，也包括0倍，所以需要考虑K<0是将K转化为正数，因为同解。

  4. K为零的情况

    K为零的情况需要特殊考虑，主要是因为算法可以大大简化为查找连续两个0的算法。也因为K为零会使求余数运算符无法使用。

  5. 循环次数过多超时问题

    此属于算法优化问题，当Sum(k+1)本身就是K的整数倍的时候，可以直接跳过K的整数倍递增的查找运算，从而避免K过小，序列元素值过大而造成的超时问题。

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
class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        //special consideration for k=0 case
        if(k == 0){
            for(int i = 0; i< nums.length; ++i){
                if(i> 0 && nums[i] == 0 && nums[i-1]==0)
                    return true;
            }
            return false;
        }
        // revert to positive value to get same solution
        if(k < 0)
            k = -k;
        
        int previous_sum = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer> ();
        int sum = 0;
        for(int i = 0; i< nums.length; ++i){
            sum += nums[i];            
            //check sum(k+1) first
            if(sum%k == 0 && i > 0)
                return true;
            //iterate to search
            int k_multiple = 0;
            while(k_multiple<sum ){
                if(map.containsKey(sum-k_multiple)){
                    if(sum-k_multiple == previous_sum && map.get(previous_sum) == 1){
                        k_multiple += k;
                        continue;
                    }                        
                    return true;
                }                    
                k_multiple += k;
            }
            

            //memroize sum(k)
            if(map.containsKey(sum))
                map.put(sum, map.get(sum)+1);
            else
                map.put(sum, 1);

            // store previoius sum(k) to avoid length=1 subarraies
            previous_sum = sum;
        }
        return false;
    }
}