求和等于给定值的子数组的累积和

Question

我试图理解以下代码背后的逻辑，但是我不清楚代码的 2 部分，部分原因是目前我还不完全清楚支持逻辑的数学。

困惑 1: 我不明白为什么我们在开始计算数组的总和之前将 0 和 count = 1 放在映射中？它有什么帮助？

混淆 2： 如果我在 if() 条件之后移动 map.put(sum, map.getOrDefault(sum)+1)，我会得到正确的解决方案。但是，如果我将它放在下面代码所示的位置，它会给出错误的结果。问题是当我们在地图中搜索 sum-k 的值以查找计数

时，为什么这个位置很重要

public int subarraySum(int[] nums, int k) {

     HashMap<Integer,Integer> prefixSumMap = new HashMap<>();
     prefixSumMap.put(0, 1); // CONFUSION 1

     int sum = 0;
     int count = 0;

     for(int i=0; i<nums.length; i++) {
         sum += nums[i];

         prefixSumMap.put(sum, prefixSumMap.getOrDefault(sum, 0)+1); //CONFUSION 2
         if(prefixSumMap.containsKey(sum - k)) {
             count += prefixSumMap.get(sum - k);
         }
     }

     return count;
 }

Answer 1

#1: put(0, 1) 很方便，因此您不必使用额外的 if 语句检查是否 sum == k。

说 k = 6 并且您输入了 [1,2,3,4]，然后在处理完 3 之后您有 sum = 6，这当然意味着子数组 [1, 2, 3] 需要计算。由于sum - k是0，get(sum - k)returns一个1加到count，这意味着我们不需要单独的if (sum == k) { count++; }

#2: prefixSumMap.put(sum, prefixSumMap.getOrDefault(sum, 0)+1) 意思是第一次看到一个和，它做一个put(sum, 1)。第二次变成put(sum, 2)，第三次变成put(sum, 3)，以此类推

基本上，该图是总和与该总和出现次数的映射。

例如如果 k = 3 且输入为 [0, 0, 1, 2, 4]，则在处理 2 时，sum = 3 且映射包含 { 0=3, 1=1, 3=1 }，因此 get(sum - k)，又名 get(0)、returns 3，因为有 3 个子数组总和为 3：[0, 0, 1, 2]、[0, 1, 2] 和 [1, 2]

类似如果 k = 4 和输入是 [1, 2, 0, 0, 4]，当 4 被处理时，sum = 7 并且映射包含 { 0=1, 1=1, 3=3, 7=1 }，所以get(sum - k)，又名 get(3)，returns 3，因为有 3 个子数组总和为 3：[0, 0, 4]、[0, 4] 和 [4]。

注意：这一切都假定值不能为负数。

Answer 2

您可能会觉得这很有趣。我修改了方法以使用 longs 来防止整数溢出导致负数。

这两种方法都适用于正数。尽管第一个要简单得多，但它们 return 测试数组的计数相同。

public static void main(String[] args) {
Random r = new Random();
long[] vals = r.longs(10_000_000, 1, 1000).toArray();
long k = 29329;
System.out.println(positiveValues(vals, k));
System.out.println(anyValues(vals, k));


public static int positiveValues(long[] array, long k) {
    
    Map<Long,Long> map = new HashMap<>(Map.of(0L,1L));
    int count = 0;
    long sum = 0;
    
    for (long v : array) {
      sum += v;
      map.put(sum,1L);
       if (map.containsKey(sum-k)) {
           count++;
       }
    }
    return count;
}

public static int anyValues(long[] nums, long k) {

     HashMap<Long,Long> prefixSumMap = new HashMap<>();
     prefixSumMap.put(0L, 1L); 

     long sum = 0;
     int count = 0;

     for(int i=0; i<nums.length; i++) {
         sum += nums[i];
         prefixSumMap.put(sum, prefixSumMap.getOrDefault(sum, 0L)+1L);
         if(prefixSumMap.containsKey(sum - k)) {
             count += prefixSumMap.get(sum - k);
         }
     }
     return count;
 }

此外，声明

    long v = prefixSumMap.getOrDefault(sum,  0L) + 1L;

对于正数数组总是 returns 1。这是因为以前的总和永远不会是 re-encountered 只有正值。

该语句以及通过从映射中获取值来计算 count 的语句是允许数组包含正数和负数。 -k 和所有正值也是如此。

对于以下输入：

long[] vals = {1,2,3,-3,0,3};

和为 3 的子数组是

(1+2), (3), (1+2+3-3), (1+2+3-3+0), (3-3+0+3), (0+3), (3)

由于添加负数会产生以前的总和，因此需要占。正值的解决方案不会这样做。

这也适用于所有负值。如果 k 为正，则将找到 no 子数组，因为所有和均为负。如果 k 为负，则可能找到一个或多个子数组 may。

求和等于给定值的子数组的累积和

Cumulative sum to find Subarrays' whose sum equals a give value

java

math

hashmap

prefix-sum