0

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

  1. 困惑 1：我不明白为什么我们要在开始查找数组的总和之前将 0 和 count = 1 放在地图中？它有什么帮助？

  2. 困惑 2：如果我map.put(sum, map.getOrDefault(sum)+1)在 if() 条件之后移动，我会得到正确的解决方案。但是，如果我把它放在下面代码所示的地方，它会给我错误的结果。问题是为什么这个位置很重要，当我们在地图中搜索 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;
 }
4

2 回答 2

0

#1: put(0, 1)是一种方便，因此您不必有额外的if语句来检查 if sum == k。

说k = 6and you have input [1,2,3,4]，然后在处理完之后3you have sum = 6，这当然意味着[1, 2, 3]需要计算子数组。因为sum - k是 0，get(sum - k)所以返回一个 1 添加到count，这意味着我们不需要单独的if (sum == k) { count++; }

#2: prefixSumMap.put(sum, prefixSumMap.getOrDefault(sum, 0)+1)表示第一次看到 sum 时，它会执行put(sum, 1). 第二次变成put(sum, 2)，第三次put(sum, 3)，以此类推。

基本上，该地图是总和到看到总和的次数的地图。

例如 ifk = 3和 input 是[0, 0, 1, 2, 4]，在2处理sum = 3完 之后，map 包含{ 0=3, 1=1, 3=1 }，所以get(sum - k)，aka get(0)，返回 3，因为有 3 个子数组的总和为 3：[0, 0, 1, 2]、[0, 1, 2]和[1, 2]

类似的 ifk = 4和 input 是[1, 2, 0, 0, 4]，当4被处理时，sum = 7映射包含{ 0=1, 1=1, 3=3, 7=1 }，所以get(sum - k)，aka get(3)，返回 3，因为有 3 个子数组总和为 3：[0, 0, 4]、[0, 4]和[4]。

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

于 2020-09-21T21:18:23.167 回答
0

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

这两种方法都适用于正数。尽管第一个更简单，但它们都为测试数组返回相同的计数。

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;

对于正数数组，始终返回 1。这是因为以前的总和永远不会再遇到仅正值。

该语句以及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

于 2020-09-22T01:52:37.737 回答