连续子阵和

Question

我在Leetcode上遇到了这个问题，我看到了解决方案，但我无法理解它为什么工作。它适用于模数的什么性质？我们怎么能说我们已经找到了一个和等于k的子数组，只看前面的模结果呢？

问题：

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

Answer 1

这实际上是一个众所周知的问题，只是对它做了一个简单的改动，如果你想的话，这里有一篇关于GFG上更简单的版本的文章：用给定的和查找子数组

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

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

您添加到映射中的数字基本上表示从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。

现在您应该了解了简单版本的解决方案，现在是解释LeetCode版本的解决方案的时候了。

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