从数组中找到等于某个值 X 的子数组

Question

背景

给定一个包含正数和负数的数组。您要在数组中找到一个等于某个值 X 的子数组。输入是数组和 X 值。输出是子数组的开始和结束索引。

例子

Array = [2,6,0,9,7,3,1,4,1,10] 

X = 15

Output = [1,3]

以下是我在geeks4geeks上找到的代码

  public static void subArraySum(int[] arr, int n, int sum) { 

        //cur_sum to keep track of cummulative sum till that point 

        int cur_sum = 0; 

        int start = 0; 

        int end = -1; 

        HashMap<Integer, Integer> hashMap = new HashMap<>(); 

        for (int i = 0; i < n; i++) { 

            cur_sum = cur_sum + arr[i]; 

            //check whether cur_sum - sum = 0, if 0 it means 

            //the sub array is starting from index 0- so stop 

            if (cur_sum - sum == 0) { 

                start = 0; 

                end = i; 

                break; 

            } 

            //if hashMap already has the value, means we already  

            // have subarray with the sum - so stop 

            if (hashMap.containsKey(cur_sum - sum)) { 

                start = hashMap.get(cur_sum - sum) + 1; 

                end = i; 

                break; 

            } 

            //if value is not present then add to hashmap 

            hashMap.put(cur_sum, i); 

        } 

        // if end is -1 : means we have reached end without the sum 

        if (end == -1) { 

            System.out.println("No subarray with given sum exists"); 

        } else { 

            System.out.println("Sum found between indexes " 

                            + start + " to " + end); 

问题 总的来说，我能够理解为什么这个解决方案有效。具有条件的第一个块cur_sum - sum == 0对我来说完全有意义。

但是，我对hashMap.containsKey(cur_sum - sum)支票有效的原因感到非常困惑。我知道它每次都有效，但我想了解它背后的数学意义。我在一篇采访博客中读到，这使用了常见的差异技术，但我不确定这如何适用于此。

在准备面试时，我并不是要记住这个解决方案，而是要对它的工作原理有一个深刻的理解。

我花了几个小时想出例子并手工追踪它们，解决方案有效，但我无法理解为什么这种技术有效，我拒绝盲目地记住它。

例如，如果我们谈论的是一个只有正数的数组，那么我知道可以使用“滑动窗口”技术并且我能够完全理解。当您扩展窗口时，总和会变大，而当您关闭窗口时，总和会变小。上述问题并非如此，因此希望得到一些帮助。

Answer 1

sum- 是我们想要达到的数字cur_sum- 是到目前为止数组中所有元素的总和比如说cur_sum - sum = x我们在开始时更新的每个步骤cur_sum，如果让您感到困惑的条件评估为false我们更新哈希图并继续。到目前为止，一切都很好。现在，为什么我们要查看是否x已经在哈希图中？答案是，如果有一个先前的索引i，其中直到该索引（包括）的所有元素的总和为x，这意味着从索引i+1到当前索引，我们有一个子数组，其总和为：cur_sum - x并且因为我们已经知道这cur_sum - sum = x意味着从i+1当前索引开始和结束的子数组总和恰好为sum.让我们以您发布的示例为例：Array&nbsp;=&nbsp;[2,6,0,9,7,3,1,4,1,10]&nbsp; X&nbsp;=&nbsp;15 Output&nbsp;=&nbsp;[1,3]让我们迭代数组：索引 0：sum 2 => 使用 (0:2)索引 1 更新地图：sum 2+6=8 => 使用 (1:8)索引 2 更新地图：sum 2+6+0 =8 => 用 (2:8)索引 3 更新地图：总和 2+6+0+9=17 =>但是现在我们可以看到映射已经包含 17-15=2 (0:2) 因此我们知道从索引 1 开始的子数组的总和（索引 1 在 (0:2) 的零之后）并结束于当前索引：3 - 这个子数组总和为 15。