连续子阵列和 [英] Continuous Subarray sum

问题描述

我在 Leetcode 上遇到了这个问题我看到了解决方案，但我无法理解它为什么起作用.它适用于模量的什么性质?我们怎么能说我们找到了一个总和等于 k ​​的子数组，仅仅通过查看模结果的前一次出现?

I came across this problem on Leetcode I saw the solution but I am unable to understand why it works. What property of modulus does it apply? How can we say that we have found a subarray with sum equal to k just by looking at the previous occurence of the modulo result?

问题:

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

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.

示例 1:输入:[23, 2, 4, 6, 7], k=6输出:真解释:因为 [2, 4] 是一个大小为 2 的连续子数组，总和为 6.

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.

问题链接

解决方案:

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

解决方案链接

推荐答案

这实际上是一个众所周知的问题，只需对其进行简单的修改，如果您想要，这里有一篇关于 GFG 更简单版本的文章:找到给定总和的子数组

This actually is a well known problem with a simple twist to it, if you want here is an article about the simpler version on GFG : Find subarray with given sum

总体思路是保留遇到的所有数字的总和并将它们插入到地图中.随着你继续检查你是否已经遇到了一个 actual_total_sum - target_sum(也就是说，你在地图中设置的值是否等于 actual_total_sum - target_sum)，如果有，您会发现自己是一个给出所需值的子数组.

The overall idea is that you keep the total sum of all the numbers encountered and insert them in a map. As you go on you check if you had already encountered a of value actual_total_sum - target_sum (that is if one on the value you set in your map is equal to actual_total_sum - target_sum), if you have, you found yourself a subarray giving the wanted value.

现在，如果你明白应该没有任何问题，但让我澄清一切以确保:

Now if you understood that there shouldn't be any problem but let me clarify everything to be sure:

您添加到地图中的数字基本上表示从 0 到 添加它们的索引" 之间所有元素的总和，因此您有整数表示索引的总计值[0,0], [0,1], [0,2],... 所以，如果您已经添加了值 actual_total_sum - target_sum，请检查您的地图你在问，是否有一对索引 [0,x] 等于 actual_total_sum - target_sum" 如果是，这意味着子数组 [x+1,actual_index] 等于 target_sum.

The numbers you are adding into your map basically represent the sum of all elements from 0 to "index at which they were added", therefore you have integers indicating the values of totals for indices [0,0], [0,1], [0,2],... SO, by checking in your map if you have already added the value actual_total_sum - target_sum you are asking, "Is there a pair of indices [0,x] being equal to actual_total_sum - target_sum" if yes, that means that the subarray [x+1, actual_index] is equal to the target_sum.

现在你应该了解更简单版本的解决方案了，现在是时候解释这个问题的 leetcode 版本的解决方案了.

Now you should understand the solution for the simpler version, it's now time to explain the solution for leetcode's version of this problem.

变化很简单，不是为子数组[0,0]、[0,1]、[0,2]、...插入total_sum值> 您插入 total_sum%k.所以，通过检查你的地图，如果你已经添加了 (actual_total_sum%k) - target_sum 你问的值，是否有一对索引 [0,x] 等于(actual_total_sum%k) - target_sum" 如果是，则表示子数组 [x+1, actual_index] 等于 target_sum 的倍数.对于问题的最后一部分，您必须确保子数组的长度 > 2 这很容易，您只需检查 actual_index-(x+1) >= 1 是否相同如解决方案中所写的 actual_index-x > 1.

The twist is simply that instead of inserting total_sum value for the subarrays [0,0], [0,1], [0,2],... you insert total_sum%k. SO, by checking in your map if you have already added the value (actual_total_sum%k) - target_sum you are asking, "Is there a pair of indices [0,x] being equal to (actual_total_sum%k) - target_sum" if yes, that means that the subarray [x+1, actual_index] is equal to a multiple of target_sum. And for the last part of the problem, you must make sure the subarray has length > 2 well that's quite easy you just have to check that actual_index-(x+1) >= 1 which is the same as actual_index-x > 1 as written in the solution.

抱歉，耽误了一些时间，解释写了一段时间，但我希望它们足够清楚，如果没有，请不要犹豫，要求澄清！

Sorry, for the delay, explanations took a while to write but I hope that they are clear enough, if not, do not hesitate to ask for clarification!

这篇关于连续子阵列和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！