从等于某个值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); 

Answer 1

sum-是我们想要实现的数字

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

假设cur_sum-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:SUM2=>用(0:2)更新地图
索引1:SUM2+6=8=>用(1:8)更新地图
索引2:SUM2+6+0=8=>用(2:8)更新地图
索引3:SUM2+6+0+9=17=>