wordpress博客主题模板免费,百度关键词网站排名优化软件,做360网站优化排,netcore网站开发实战文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】
前缀和
二【题目难度】
中等
三【题目编号】
523.连续的子数组和
四【题目描述】
给你一个… 文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】
前缀和
二【题目难度】
中等
三【题目编号】
523.连续的子数组和
四【题目描述】
给你一个整数数组 nums 和一个整数 k 如果 nums 有一个 好的子数组 返回 true 否则返回 false一个 好的子数组 是 长度 至少为 2 且子数组元素总和为 k 的倍数。 注意 子数组 是数组中 连续 的部分。如果存在一个整数 n 令整数 x 符合 x n * k 则称 x 是 k 的一个倍数。0 始终 视为 k 的一个倍数。
五【题目示例】 示例 1 输入nums [23,2,4,6,7], k 6输出true解释[2,4] 是一个大小为 2 的子数组并且和为 6 。 示例 2 输入nums [23,2,6,4,7], k 6输出true解释[23, 2, 6, 4, 7] 是大小为 5 的子数组并且和为 42 。 42 是 6 的倍数因为 42 7 * 6 且 7 是一个整数。 示例 3 输入nums [23,2,6,4,7], k 13输出false
六【题目提示】 1 n u m s . l e n g t h 1 0 5 1 nums.length 10^5 1nums.length105 0 n u m s [ i ] 1 0 9 0 nums[i] 10^9 0nums[i]109 0 s u m ( n u m s [ i ] ) 2 31 − 1 0 sum(nums[i]) 2^{31} - 1 0sum(nums[i])231−1 1 k 2 31 − 1 1 k 2^{31} - 1 1k231−1
七【解题思路】
前缀和思想设 prefix_sum[i] 表示数组 nums 的前缀和即 prefix_sum[i] 表示 nums 从第 0 到第 i 的元素的和。对于任意两个下标 i 和 ji j子数组 nums[i1:j1] 的和可以表示为 prefix_sum[j] - prefix_sum[i]。取模运算我们需要找到两个前缀和 prefix_sum[j] 和 prefix_sum[i]使得它们的差 prefix_sum[j] - prefix_sum[i] 是 k 的倍数。我们可以通过对前缀和取模的方式哈希表来简化这个问题如果 prefix_sum[j] % k prefix_sum[i] % k那么 prefix_sum[j] - prefix_sum[i] 一定是 k 的倍数同余定理。边界情况处理 如果 k 0则子数组的和必须为 0所以需要特判。由于子数组的长度至少为 2所以当找到满足条件的前缀和时还需要确保两个下标之间的距离大于等于 2。 最后返回结果即可具体细节可以参考下面的代码
八【时间频度】
时间复杂度 O ( m ) O(m) O(m) m m m为传入的数组的长度空间复杂度 O ( m i n ( m , k ) ) O(min(m, k)) O(min(m,k)) m m m为传入的数组的长度 k k k为计算得到的余数的个数
九【代码实现】
Java语言版
class Solution {public boolean checkSubarraySum(int[] nums, int k) {// 用于存储取模后的前缀和与其下标, 初始化表示前缀和为0时在-1位置HashMapInteger, Integer hashMap new HashMapInteger, Integer();hashMap.put(0, -1);// 初始化前缀和int prefixSum 0;for (int i 0; i nums.length; i) {// 更新前缀和prefixSum nums[i];if (k ! 0) {// 对 k 取模prefixSum % k;}// 检查当前取模后的前缀和是否已经在哈希表中if (hashMap.containsKey(prefixSum)) {// 如果存在并且下标差大于等于 2则找到符合条件的子数组if (i - hashMap.get(prefixSum) 1) {return true;}} else {// 不存在则记录当前前缀和对应的下标hashMap.put(prefixSum, i);}}return false;}
}Python语言版
class Solution:def checkSubarraySum(self, nums: List[int], k: int) - bool:# 用于存储取模后的前缀和与其下标, 初始化表示前缀和为0时在-1位置hash_map {0: -1}# 初始化前缀和prefix_sum 0for i, num in enumerate(nums):# 更新前缀和prefix_sum numif k ! 0:# 对 k 取模prefix_sum % k# 检查当前取模后的前缀和是否已经在哈希表中if prefix_sum in hash_map:# 如果存在并且下标差大于等于 2则找到符合条件的子数组if i - hash_map[prefix_sum] 1:return Trueelse:# 不存在则记录当前前缀和对应的下标hash_map[prefix_sum] ireturn FalseC语言版
class Solution {
public:bool checkSubarraySum(vectorint nums, int k) {// 用于存储取模后的前缀和与其下标, 初始化表示前缀和为0时在-1位置unordered_mapint, int hashMap;hashMap[0] -1;// 初始化前缀和int prefixSum 0;for (int i 0; i nums.size(); i) {// 更新前缀和prefixSum nums[i];if (k ! 0) {// 对 k 取模prefixSum % k;}// 检查当前取模后的前缀和是否已经在哈希表中if (hashMap.find(prefixSum) ! hashMap.end()) {// 如果存在并且下标差大于等于 2则找到符合条件的子数组if (i - hashMap[prefixSum] 1) {return true;}} else {// 不存在则记录当前前缀和对应的下标hashMap[prefixSum] i;}}return false;}
};十【提交结果】 Java语言版 Python语言版 C语言版
