专栏首页眯眯眼猫头鹰的小树杈leetcode523. Continuous Subarray Sum

leetcode523. Continuous Subarray Sum

题目要求

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 a 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.

假设有一个非负整数数组,要求找到其中一个连续的子数组,该子数组中所有元素的和是k的整数倍。要求连续子数组的长度大于等于2.

思路一:暴力循环

如果我们可以计算出所有长度大于等于2的连续子数组的元素和,就可以判断出是否存在满足题意的子数组。这里可以做一个简单的优化,即用一个额外的数组用来存[0..i]的子数组的元素和,则sum[i..j]的子数组的元素和可以通过sum[0..j+1]-sum[0..i-1]计算得出。代码如下:

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

思路二:记录中间结果

基于思路一的基础上可以进一步优化,既然我们要计算的是k的整数倍的子数组和,而我们有的是可以通过O(N)的时间复杂度计算出[0...i]子数组的元素和。那么我们可以推算出,假如sum[0..j]%k = m,而sum[0..i]%k = m(i-j>=2),那么可以知道[i+1, j]这个子数组一定是k的整数倍。因此我们只需要记录已经遍历过的从0下标开始的所有子数组的和以及对应的下标值,并且判断是否存在如上述的关联即可。

public boolean checkSubarraySum2(int nums[], int k){  
  
    Map<Integer,Integer> map = new HashMap<>();  
    map.put(0,-1);  
    int sumSoFar = 0;  
    for(int i=0; i < nums.length; i++){  
        sumSoFar = sumSoFar + nums[i];  
        if(k != 0) sumSoFar = sumSoFar % k;  
        if(map.containsKey(sumSoFar)){  
            int start = map.get(sumSoFar);  
            if(i-start > 1) return true;  
        }else{  
            map.put(sumSoFar, i);  
        }  
    }  
    return false;  
}

思路三:分治法

分治法在这题的核心思想在于,将整个数组先一分为二,分别判断在左子数组和右子数组中是否存在满足条件的子数组,如果没有,再判断跨左右子数组的子数组是否存在满足条件的连续子数组。分治法和动态规划都在于想通递归场景后,代码就行云流水了。

public boolean checkSubarraySum(int[] nums, int lo, int hi, int k){  
    if(lo==hi) return false;  
    int mid = lo+(hi-lo)/2;  
    if(checkSubarraySum(nums, lo, mid, k)) return true;  
    if(checkSubarraySum(nums, mid+1, hi, k)) return true;  
    int left = mid, right = mid+1;  
    int sum = nums[left];  
    while(left>=lo&&right<=hi){  
        sum += nums[right];  
        if((k>0&&sum%k==0)||(k==0&&sum==0)) return true;  
        --left;  
        ++right;  
        if(left>=lo){  
            sum += nums[left];  
            if((k>0&&sum%k==0)||(k==0&&sum==0))  return true;  
        }  
    }  
    return false;  
}  
public boolean checkSubarraySum(int[] nums, int k) {  
    k = Math.abs(k);  
    return checkSubarraySum(nums, 0, nums.length-1, k);  
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode368. Largest Divisible Subset

    假设有一组值唯一的正整数数组,找到元素最多的一个子数组,这个子数组中的任选两个元素都可以构成Si % Sj = 0 或 Sj % Si = 0。

    眯眯眼的猫头鹰
  • leetcode363. Max Sum of Rectangle No Larger Than K

    现有一个由整数构成的矩阵,问从中找到一个子矩阵,要求该子矩阵中各个元素的和为不超过k的最大值,问子矩阵中元素的和为多少? 注:后面的文章中将使用[左上角顶点坐标...

    眯眯眼的猫头鹰
  • leetcode410. Split Array Largest Sum

    将一个长度为n的正整数数组分割为m个非空的连续子数组,并分别计算每个子数组中所有元素的和。求一种分割方式,使得该分割方式生成的最大子数组和为所有分割方式中最小的...

    眯眯眼的猫头鹰
  • LeetCode. 209. 长度最小的子数组

    给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0...

    宇宙之一粟
  • 分割等和子集

    给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

    宇宙之一粟
  • 面试中可能被问到的常用排序算法

    排序算法是一种比较简单的算法,从我们一开始接触计算机编程开始接触的可能就是排序或者搜索一类的算法,但是因为排序在其他的一些算法中应用较多,所以为了提高性能已经研...

    本人秃顶程序员
  • 只出现一次的元素

    给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

    木瓜煲鸡脚
  • 删除排序数组中的重复数字Ⅱ

    一份执着✘
  • LeetCode算法题(一)

    请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。

    万能青年
  • [LeetCode] 938. Range Sum of BST 二叉搜索树的区间和

    Given the root node of a binary search tree, return the sum of values of all nod...

    lucifer210

扫码关注云+社区

领取腾讯云代金券