先来详细描述下这道题。在一个全为正整数的数组中找到总和为给定值的子数组，给出子数组的起始下标（闭区间），举个例子：
在[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分的答案，而后再想方法把分数晋升下来，别最初交了白卷。 给出一个可行解，而后再继续迭代优化，我感觉这也是解决一个简单问题比拟好的思路。
最初送大家一句鸡汤，没有人生下来就是王者，只是一直的致力成为了王者罢了。
欢送关注我的面试专栏中高级程序猿面试题精选，继续更新，永恒收费，本专栏会继续收录我遇到的中高级程序猿经典面试题，除了提供详尽的解题思路外，还会从面试官的角度提供扩大题，是大家面试进阶的不二之选，心愿能帮忙大家找到更好的工作。另外，也征集面试题，如果你遇到了不会的题 私信通知我，有价值的题我会给你出一篇博客。
发表回复