领导视察网站建设/百度爱采购平台官网

523. 连续的子数组和

难度中等107

给定一个包含非负数的数组和一个目标整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，总和为 k 的倍数，即总和为 n*k，其中 n 也是一个整数。

示例 1:

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

示例 2:

输入: [23,2,6,4,7], k = 6
输出: True
解释: [23,2,6,4,7]是大小为 5 的子数组，并且和为 42。

解题思路，求出前i项的前缀和，然后用一个j进行区间划分进行遍历

class Solution {public boolean checkSubarraySum(int[] nums, int k) {int sum = 0;int [] curSum = new int[nums.length+1];for(int i = 0;i<nums.length;i++){sum += nums[i];curSum[i+1] = sum;}for(int i = 0;i<curSum.length;i++){for(int j = i+2;j<curSum.length;j++){int temp = curSum[j] - curSum[i];if((temp == 0 && k == 0) || (k != 0 && temp % k == 0)){return true;}}}return false;}
}

解题思路二：我用dp数组存储每一种可能。然后遍历，但是有错，希望大家纠正