累积求和以找到和为给定值的子数组

huangapple go评论62阅读模式
英文:

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

问题

我试图理解以下代码背后的逻辑,然而对于代码中的两个部分我不太清楚,部分因为支持逻辑的数学内容目前对我来说不是很清晰。

  1. 困惑 1: 我不明白为什么在我们开始计算数组的和之前,我们会在映射中放入值为 0,计数为 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); // 困惑 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); // 困惑 2
             if(prefixSumMap.containsKey(sum - k)) {
                 count += prefixSumMap.get(sum - k);
             }
         }
    
         return count;
     }
    
英文:

I'm trying to understand the logic behind the following code however I'm unclear about 2 parts of the code partially because the math supporting the logic is not totally clear to me at this moment.

  1. CONFUSION 1: I don't understand why would we put 0 with count = 1 in the map before we start finding the sum of the array? How does it help?

  2. CONFUSION 2: If I move the map.put(sum, map.getOrDefault(sum)+1) after the if() condition, I get the correct solution. However if I put it at the place as shown in the code below, it gives me wrong result. The question is why does the position of this matters, when we're searching for the value of sum-k in the map for finding the count

    public int subarraySum(int[] nums, int k) {
    
         HashMap&lt;Integer,Integer&gt; prefixSumMap = new HashMap&lt;&gt;();
         prefixSumMap.put(0, 1); // CONFUSION 1
    
         int sum = 0;
         int count = 0;
    
         for(int i=0; i&lt;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;
     }
    

答案1

得分: 0

#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)返回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),返回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),返回3,因为有3个子数组的和为3:[0, 0, 4][0, 4],和[4]

*注意:*这一切都假设值不能为负数。

英文:

#1: put(0, 1) is a convenience so you don't have to have an extra if statement checking if sum == k.

Say k = 6 and you have input [1,2,3,4], then after you've processed the 3 you have sum = 6, which of course means that subarray [1, 2, 3] needs to be counted. Since sum - k is 0, get(sum - k) returns a 1 to add to count, which means we don't need a separate if (sum == k) { count++; }

#2: prefixSumMap.put(sum, prefixSumMap.getOrDefault(sum, 0)+1) means that the first time a sum is seen, it does a put(sum, 1). The second time, it becomes put(sum, 2), third time put(sum, 3), and so on.

Basically the map is a map of sum to the number of times that sum has been seen.

E.g. if k = 3 and input is [0, 0, 1, 2, 4], by the time the 2 has been processed, sum = 3 and the map contains { 0=3, 1=1, 3=1 }, so get(sum - k), aka get(0), returns 3, because there are 3 subarrays summing to 3: [0, 0, 1, 2], [0, 1, 2], and [1, 2]

Similar if k = 4 and input is [1, 2, 0, 0, 4], by the time the 4 has been processed, sum = 7 and the map contains { 0=1, 1=1, 3=3, 7=1 }, so get(sum - k), aka get(3), returns 3, because there are 3 subarrays summing to 3: [0, 0, 4], [0, 4], and [4].

Note: This all assumes that values cannot be negative.

答案2

得分: 0

你可能会发现这很有趣。我修改了方法,使用 long 型变量来防止整数溢出,从而导致出现负数。

这两种方法对于正数都能很好地工作。尽管第一种方法简单得多,但它们对于测试数组返回的计数是相同的。

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 是正数,则不会找到子数组的和,因为所有和将为负数。如果 k 是负数,则可能会找到一个或多个子数组的和。

英文:

You may find this interesting. I modified the method to use longs to prevent integer overflow resulting in negative numbers.

Both of these methods work just fine for positive numbers. Even though the first one is much simpler, they both return the same count for the test array.

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&lt;Long,Long&gt; map = new HashMap&lt;&gt;(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&lt;Long,Long&gt; prefixSumMap = new HashMap&lt;&gt;();
prefixSumMap.put(0L, 1L); 
long sum = 0;
int count = 0;
for(int i=0; i&lt;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;
}

Additionally, the statement

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

Always returns 1 for positive arrays. This is because previous sums can never be re-encountered for positive only values.

That statement, and the one which computes count by taking a value from the map is to allow the array to contain both positive and negative numbers. And ths same is true a -k and all positive values.

For the following input:

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

The subarrays that sum to 3 are

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

Since adding negative numbers can result in previous sums, those need to be
accounted for. The solution for positive values does not do this.

This will also work for all negative values. If k is positive, no subarray will be found since all sums will be negative. If k is negative one or more subarrays may possibly be found.

huangapple
  • 本文由 发表于 2020年9月22日 04:24:50
  • 转载请务必保留本文链接:https://go.coder-hub.com/63999511.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定