从数组中找到等于某个值 X 的子数组
Find a subarray from a array that equals some value X
背景
给你一个包含正数和负数的数组。
你要在数组中找到一个等于某个值 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)
检查为何有效感到非常困惑。我知道它每次都有效,但我想了解它背后的数学意义。我在一篇采访博客中读到,这使用了常见的差异技术,但我不确定这如何适用于此。
在准备面试时,我并不是要记住这个解决方案,而是要深入了解它的工作原理。
我花了几个小时想出例子并手工追踪它们,解决方案有效,但我无法理解为什么这种技术有效,我拒绝盲目地记住它。
例如,如果我们谈论的是一个只有正数的数组,那么我知道可以使用 "SLIDING WINDOW" 技术并且我能够完全理解。当您扩展 window 时,总和会变大,当您关闭 window 时,总和会变小。上述问题并非如此,因此希望得到一些帮助。
sum
——就是我们要达到的数字
cur_sum
- 是到目前为止数组中所有元素的总和
说 cur_sum - sum = x
我们在开始时更新 cur_sum
的每个步骤,如果让您感到困惑的条件评估为 false
我们更新哈希图并继续。
到目前为止一切顺利。
现在,我们为什么要查看 x
是否已经在 hashmap 中?
答案是,如果有一个先前的索引 i
,直到该索引(包括)的所有元素的总和为 x
,这意味着从索引 [=19] =] 直到当前索引,我们有一个子数组,其总和为: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]
让我们迭代数组:
index 0: sum 2 => 用 (0:2)
更新地图
索引 1:总和 2+6=8 => 用 (1:8)
更新地图
索引 2:总和 2+6+0=8 => 用 (2:8)
更新地图
索引 3:总和 2+6+0+9=17 =>
但现在我们可以看到地图已经包含 17-15=2 (0:2)
因此我们知道从索引 1 开始(索引 1 在 (0:2) 的零之后)并在当前索引结束的子数组的总和:3 - 这个子数组总和为 15.
背景
给你一个包含正数和负数的数组。 你要在数组中找到一个等于某个值 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)
检查为何有效感到非常困惑。我知道它每次都有效,但我想了解它背后的数学意义。我在一篇采访博客中读到,这使用了常见的差异技术,但我不确定这如何适用于此。
在准备面试时,我并不是要记住这个解决方案,而是要深入了解它的工作原理。
我花了几个小时想出例子并手工追踪它们,解决方案有效,但我无法理解为什么这种技术有效,我拒绝盲目地记住它。
例如,如果我们谈论的是一个只有正数的数组,那么我知道可以使用 "SLIDING WINDOW" 技术并且我能够完全理解。当您扩展 window 时,总和会变大,当您关闭 window 时,总和会变小。上述问题并非如此,因此希望得到一些帮助。
sum
——就是我们要达到的数字
cur_sum
- 是到目前为止数组中所有元素的总和
说 cur_sum - sum = x
我们在开始时更新 cur_sum
的每个步骤,如果让您感到困惑的条件评估为 false
我们更新哈希图并继续。
到目前为止一切顺利。
现在,我们为什么要查看 x
是否已经在 hashmap 中?
答案是,如果有一个先前的索引 i
,直到该索引(包括)的所有元素的总和为 x
,这意味着从索引 [=19] =] 直到当前索引,我们有一个子数组,其总和为: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]
让我们迭代数组:
index 0: sum 2 => 用 (0:2)
更新地图
索引 1:总和 2+6=8 => 用 (1:8)
更新地图
索引 2:总和 2+6+0=8 => 用 (2:8)
更新地图
索引 3:总和 2+6+0+9=17 =>
但现在我们可以看到地图已经包含 17-15=2 (0:2) 因此我们知道从索引 1 开始(索引 1 在 (0:2) 的零之后)并在当前索引结束的子数组的总和:3 - 这个子数组总和为 15.