java - 从数组中查找等于某个值 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 的 block 对我来说完全有意义。

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

在准备面试时，我并不是试图记住这个解决方案，而是试图深入了解它为何有效。

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

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

Answer 1

sum - 是我们想要达到的数字

cur_sum - 是迄今为止数组中所有元素的总和

说cur_sum - sum = x

我们在每一步开始时都会更新 cur_sum，如果令您困惑的条件评估为 false，我们会更新 HashMap 并继续。

到目前为止一切顺利。

现在，我们为什么要查看 x 是否已经在 HashMap 中？

答案是，如果有一个先前的索引i，直到该索引(包括)的所有元素的总和为x，这意味着从索引i+1到当前索引，我们有一个子数组，其总和为:cur_sum - x

由于我们已经知道 cur_sum - sum = x，这意味着从 i+1 开始并在当前索引结束的子数组的总和恰好等于 sum。

让我们以您发布的示例为例:

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

让我们迭代数组:
索引 0: sum 2 => 使用 (0:2) 更新 map
索引 1: sum 2+6=8 => 用 (1:8) 更新 map
索引 2: sum 2+6+0=8 => 用 (2:8) 更新 map
索引 3:总和 2+6+0+9=17 =>

但是现在我们可以看到 map 已经包含 17-15=2 (0:2) 因此我们知道从索引 1 开始(索引 1 在 (0:2) 中的零之后)到当前索引结束的子数组的总和:3 - 该子数组的总和为 15。