[leetcode] 523. Continuous Subarray Sum - TstsUgeg的博客 - 博客频道 - CSDN.NET

[leetcode] 523. Continuous Subarray Sum - TstsUgeg的博客 - 博客频道 - CSDN.NET

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.  

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.

这道题是判断数组中是否有长度至少为2且相加和是k的倍数的子数组，题目难度为Medium。

比较直观的想法是从长度2开始依次计算所有子数组的相加和，判断其是否是k的倍数。这里不必每轮循环都重新计算相加和，可以通过动态规划的思想在上一轮循环的基础上再加一个数组元素来计算当前循环中的相加和。题目的边界情况比较多，需要注意以下几点：

• 子数组长度至少为2；

• k可能为0；

• n可能为0；

Read full article from [leetcode] 523. Continuous Subarray Sum - TstsUgeg的博客 - 博客频道 - CSDN.NET