java - 连续子数组和

Question

我在 Leetcode 上遇到了这个问题，我看到了解决方案，但我无法理解它为什么有效。它适用于什么性质的模量？我们怎么能仅仅通过查看前面出现的取模结果就说我们找到了一个和等于 k ​​的子数组呢？

问题:

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

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

Question Link

解决方案:

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;
 }

Solution Link

Answer 1

这实际上是一个众所周知的问题，只是对其进行了简单的改动，如果你想的话，这里有一篇关于 GFG 上更简单版本的文章:Find subarray with given sum

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

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

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

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

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

抱歉，由于延迟，解释花了一些时间才写出来，但我希望它们足够清楚，如果没有，请不要犹豫，要求澄清!