时间戳

首页 > 解决方案 > 连续子数组和

java - 连续子数组和

问题描述

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

问题：

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

示例 1： 输入：[23, 2, 4, 6, 7], k=6 输出：True 解释：因为 [2, 4] 是一个大小为 2 且总和为 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;
 }

解决方案链接

标签： javamodulus

解决方案

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

总体思路是保留遇到的所有数字的总和并将它们插入到地图中。当你继续检查你是否已经遇到了一个值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相同如解决方案中所写。

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

推荐阅读