内涵图网站源码,最新引流推广方法,网页的响应式布局,桂林网站优化注意事项题目 给定一个包含非负数的数组和一个目标整数 k#xff0c;编写一个函数来判断该数组是否含有连续的子数组#xff0c;其大小至少为 2#xff0c;总和为 k 的倍数#xff0c;即总和为 n*k#xff0c;其中 n 也是一个整数。 示例 1: 输入: [23,2,4,6,7], k 6 输出: True …题目 给定一个包含非负数的数组和一个目标整数 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。 说明: 数组的长度不会超过10,000。 你可以认为所有数字总和在 32 位有符号整数范围内。 来源力扣LeetCode 链接https://leetcode-cn.com/problems/continuous-subarray-sum 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 解答
class Solution {public boolean checkSubarraySum(int[] nums, int k) {if (nums null || nums.length 2) {return false;}k Math.abs(k);if (k 1) {return true;}int zLength nums.length - 1;for (int i 1; i zLength; i) {if (nums[i] 0 nums[i 1] 0) {return true;}}int length nums.length;int[][] sums new int[length][length];int iLength nums.length;sums[0][0] mod(nums[0], k);for (int i 1; i iLength; i) {int jLength i 1;if (i iLength) {jLength iLength;}for (int j 0; j jLength; j) {sums[j][i] mod(mod(nums[i], k) sums[j][i - 1], k);if (i j) {continue;}if (sums[j][i] 0) {return true;}}}return false;}public int mod(int value, int k) {if (value 0) {return 0;}if (value k) {return 0;}if (k 0) {return value;}if (value k) {return value % k;}return value;}
}要点 有如下关键点
k有可能为负数。由于求余运算占用资源比较高因此需要依据求余运算的特点自定义一个方法提高效率。当然运算效率的问题这里存疑。需要对求余运算有一定的了解比如 0对任意k求余余数均为0。因此连续的两个0,符合本题目的要求。非零整数对0求余时运算时报除0异常。mod(AB) mod(mod(A) mod(B))利用本公式可以提升运算效率节省一定的时间。
发表一点个人的看法这道题的示例2的说明有点小问题[2, 6, 4]是大小为3的子数组并且和为12恰好满足要求。
准备的用例如下 Testpublic void test01() {int[] nums new int[] { 23, 2, 4, 6, 7 };int k 6;assertTrue(new L523().checkSubarraySum(nums, k));}Testpublic void test0101() {int[] nums new int[] { 1, 2, 5, 6, 8 };int k 6;assertFalse(new L523().checkSubarraySum(nums, k));}Testpublic void test02() {int[] nums new int[] { 23, 2, 6, 4, 7 };int k 6;assertTrue(new L523().checkSubarraySum(nums, k));}Testpublic void test03() {int[] nums new int[] { 21, 2, 5, 4, 10 };int k 6;assertTrue(new L523().checkSubarraySum(nums, k));}Testpublic void test0301() {int[] nums new int[] { 21, 2, 5, 4, 7 };int k 6;assertTrue(new L523().checkSubarraySum(nums, k));}Testpublic void test0302() {int[] nums new int[] { 21, 2, 5, 4, 3 };int k 6;assertTrue(new L523().checkSubarraySum(nums, k));}Testpublic void test0303() {int[] nums new int[] { 21, 2, 5, 4, 2 };int k 6;assertTrue(new L523().checkSubarraySum(nums, k));}Testpublic void test0304() {int[] nums new int[] { 21, 2, 5, 4, 6 };int k 6;assertFalse(new L523().checkSubarraySum(nums, k));}Testpublic void test04() {int[] nums new int[] { 23, 2, 4, 6, 7 };int k -6;assertTrue(new L523().checkSubarraySum(nums, k));}Testpublic void test05() {int[] nums new int[] { 0,0 };int k 0;assertTrue(new L523().checkSubarraySum(nums, k));}Testpublic void test06() {int[] nums new int[] { 23, 2, 4, 6, 7 };int k 0;assertFalse(new L523().checkSubarraySum(nums, k));}Testpublic void test0601() {int[] nums new int[] { 23, 0, 4, 0, 7 };int k 0;assertFalse(new L523().checkSubarraySum(nums, k));}Testpublic void test0602() {int[] nums new int[] { 23, 0, 0, 2, 7 };int k 0;assertTrue(new L523().checkSubarraySum(nums, k));}Testpublic void test07() {int[] nums new int[] { 3,8,8,9,2,5,2,0,0,1,8,9,3,5,7,5,3,2,2,8,6,6 };int k 750;assertTrue(new L523().checkSubarraySum(nums, k));}
