我在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

最佳答案

实际上,这是一个众所周知的问题,但有一个简单的变化,如果您想在此处找到有关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版本说明解决方案了。

唯一的区别是,您没有为子数组 [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

抱歉,耽搁了一段时间,写了一些解释,但我希望它们很清楚,如果不能的话,请不要犹豫,要求澄清!

09-30 14:01
查看更多