共计 3969 个字符，预计需要花费 10 分钟才能阅读完成。
先来详细描述下这道题。在一个全为 正整数 的数组中找到总和为给定值的子数组，给出子数组的起始下标（闭区间），举个例子：
在 [3 2 1 2 3 4 5] 这个数组中，和为 10 的子数组是[1 2 3 4]，所以答案应该是[2,5]。
和为 15 的子数组是[1 2 3 4 5]，答案为[2,6]。
这是一道十分有意思的题，为什么这么说？最简略的解法只有具备根本的编程常识就能写出，更优的解法须要你有数据结构和算法能力，越高效的解法越奇妙，可能你一下子无奈想出所有的解法，但我置信你看完这篇博客肯定会感叹算法的神奇。
回到这道题上来，实际上它有着O(n^3)、O(n^2)、O(nlogn)、O(n) 4 种工夫复杂度的解法，如果算上空间复杂度的差别的话总共 5 种解法，我感觉还是比拟能考查到一个人的算法程度的。接下来让我率领大家由简入难看下从青铜到王者的 5 种解法，带大家吊打面试官。
这里咱们设输出参数为(arr[],target)，后续代码中我会用 s 和 e 来别离示意起始和终止地位。另外为了简化代码思路，咱们假如给定的参数里最多只有一个解（实际上多个解也不难，但会让代码变长，不利于形容思路，多解的状况就留给你当课后作业了）。
青铜 - 暴力求解
首先当然是最简略的暴力求解了，遍历起始地位 s 和完结地位 e，而后求 s 和 e 之间所有数字的和。三层循环简略粗犷，不须要任何的技巧，置信你大一刚学会编程就能解进去。
public int[] find(int[] arr, int target) {for (int s = 0; s < arr.length; s++) {for (int e = s+1; e < arr.length; e++) {
int sum = 0;
for (int k = s; k <= e; k++) { // 求 s 到 e 之间的和
sum += arr[k];
}
if (target == sum) {return new int[]{s, e};
}
}
}
return null;
}咱们来剖析下工夫复杂度，很显著是 O(n^3)，当 n 超过 1000 时就会呈现肉眼可见的慢，想想如何优化？
白银 - 空间换工夫
下面代码中，咱们每次都须要算从 s 到 e 之间的数组的和 sum[s,e]，假如我之前曾经求过了 [1,10] 之间的和 sum[1,10]，当初要求 [2,10] 之间的和 sum[2,10]，显然这两头有很大一部分是重叠的(sum[2,10])，能不能把这部分反复扫描给打消掉？这里就须要做下奇妙的变换了。
实际上 sum[s, e] = sum[0, e] - sum[0, s-1], sum[0,i] 咱们能够事后保留下来，而后重复使用。实际上 sum 数组咱们能够通过一遍数据预处理获取到。上图中，arr 蓝色区域的和正好等于 sum 数组中红色减去绿色，即sum(arr[3]-arr[7]) = sum[7]-sum[2]。
回到代码上来，编码实现中我用了额定一个数组 arrSum 来存储 0 到 i(0<=i<n)之间所有的和，为了解决不便 sumArr 下标从 1 开始，sumArr[i]示意远数组中 sum[0, i-1]。有了 sumArr 之后，sum[s,e]就能够通过 sumArr[e+1]-sumArr[s]间接获取到。残缺代码如下：
public int[] find(int[] arr, int target) {int[] sumArr = new int[arr.length + 1];
for (int i = 1; i < sumArr.length; i++) {sumArr[i] = sumArr[i-1] + arr[i-1]; // 预处理，获取累计数组
}
for (int s = 0; s < arr.length; s++) {for (int e = s+1; e < arr.length; e++) {if (target == sumArr[e+1] - sumArr[s]) {return new int[]{s, e};
}
}
}
return null;
}通过上述用空间换工夫的形式，咱们能够间接将工夫复杂度从O(n^3) 升高到O(n^2)。
黄金 - 二分查找
仔细的你可能曾经发现了，因为给出的 arr 都是正整数，所以 sumArr 肯定是递增且有序的，对于有序的数组，咱们能够间接采纳二分查找。对于这道题而已，咱们能够遍历终点 s，然在 sumArr 中二分去查找是否有起点 e，如果 s 对于的 e 存在，那么 sumArr[e]肯定等于 sumArr[s] + target，革新后的代码如下，相比于下面代码，减少了二分查找。
public int[] find(int[] arr, int target) {int[] sumArr = new int[arr.length + 1];
for (int i = 1; i < sumArr.length; i++) {sumArr[i] = sumArr[i-1] + arr[i-1];
}
for (int s = 0; s < arr.length; s++) {int e = bSearch(sumArr, sumArr[s] + target);
if (e != -1) {return new int[]{s, e};
}
}
return null;
}
// 二分查找
int bSearch(int[] arr, int target) {
int l = 1, r = arr.length-1;
while (l < r) {int mid = (l + r) >> 1;
if (arr[mid] >= target) {r = mid;} else {l = mid + 1;}
}
if (arr[l] != target) {return -1;}
return l - 1;
}由此，咱们又持续将工夫简单从 O(n^2)升高到了 O(nlogn)。
钻石 -HashMap 优化
有序数组的查找除了能够用二分优化，还能够用 hashMap 来优化，借助 HashMap O(1)的查问工夫复杂度。咱们又一次用空间来换取了工夫。
public int[] find(int[] arr, int target) {int[] sumArr = new int[arr.length + 1];
Map<Integer, Integer> map = new HashMap<>();
for (int i = 1; i < sumArr.length; i++) {sumArr[i] = sumArr[i-1] + arr[i-1];
map.put(sumArr[i], i-1);
}
for (int s = 0; s < arr.length; s++) {int e = map.getOrDefault(sumArr[s]+target, -1);
if (e != -1) {return new int[]{s, e};
}
}
return null;
}咱们终于将工夫复杂度升高到了 O(n)，这可是质的飞跃。
王者 - 尺取法
别急，还没完结，对于这道题还有王者解法。上文中咱们通过一直的优化，将工夫复杂度从 O(n^3)一步步升高到了，但咱们却一步步减少了存储的应用，从开始新增的 sumArr 数字，到最初的又减少的 HashMap，空间复杂度从 O(1)变为了 O(n)。有没有方法把空间复杂度也给将下来？我能写到这那必然是有的。
这种算法叫做尺取法。尺取法，这个名字有点难了解。咱们间接举个具体的例子，假如有 n 调长度不一的绳子并列放在一起，你须要找出其中间断的一部分绳子组成一条长度为 target 的绳子，这里须要留神是间断。这时候你能够找一个长度为 target 的尺子，而后把绳子一段段往尺子上放，如果发现短了就往后面再接一根，如果发现长了，就把最头上的一根扔掉，直到长度恰好适合。
在应用中咱们并不需要这把尺子，只须要拿 target 作为标尺即可。说起来可能比拟难了解，间接举个例子，下图演示了从数组中找到和为 22 的子数组的过程。
只有小了就右加，大了就左减，直到找到指标。
为什么尺取法是对的？我了解尺取法其实是解法二白银解法的一种优化，也是遍历了终点 s，然而对起点 e 不做有效的遍历，如果 e 到某个地位后曾经超了，因为数组里都是负数，再往后必定是超的，也就没必要持续遍历 e 了。转而去调整 s，如果 s 右移到某个地位后总和小了，s 再往右总和只会更小，也就没必要持续调整 s 了…… 整个过程就像是先固定 s 去遍历 e，而后固定 e 再去遍历 s ……，直到失去后果。
尺取法可用的根底在于 e 往右挪动总和肯定是增的，s 往右移总和肯定是减的，也就是说数组中所有的数必须是正的。没有完满的算法能够解决任何问题，但对于特定的问题肯定有最完满的解法。
说完尺取法，咱们来看下用尺取法是如何解决这道题的，代码比较简单，如下：
public int[] find(int[] arr, int target) {
int s = 0, e = 0;
int sum = arr[0];
while (e < arr.length) {if (sum > target) {sum -= arr[s++];
} else if (sum < target) {sum += arr[++e];
} else {return new int[]{s, e};
}
}
return null;
}只有一层循环，工夫复杂度 O(n)。没有额定的空间占用，空间复杂度 O(1)，这就是最完满的解法。
总结
这道算法题乍看简略，细看其实真的不简略。可能你面试遇到，没方法一下子想到最优的解，但给出一个可行的解总比没有解强。我之前面试问他人这个题，他一上来就是想着怎么最优解决，反而连最简略的青铜解法都没写进去。记得下次面试，切实是解不进去就先给个 60 分的答案，而后再想方法把分数晋升下来，别最初交了白卷。 给出一个可行解，而后再继续迭代优化，我感觉这也是解决一个简单问题比拟好的思路。
最初送大家一句鸡汤，没有人生下来就是王者，只是一直的致力成为了王者罢了。
欢送关注我的面试专栏中高级程序猿面试题精选，继续更新，永恒收费，本专栏会继续收录我遇到的中高级程序猿经典面试题，除了提供详尽的解题思路外，还会从面试官的角度提供扩大题，是大家面试进阶的不二之选，心愿能帮忙大家找到更好的工作。另外，也征集面试题，如果你遇到了不会的题 私信通知我，有价值的题我会给你出一篇博客。
