5种解法的算法面试题来看看你是青铜还是王者?

短命女 2021-09-23 04:54 218阅读 0赞

先来详细描述下这道题。在一个全为**正整数**的数组中找到总和为给定值的子数组，给出子数组的起始下标（闭区间），举个例子：

> 在\[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\])，能不能把这部分重复扫描给消除掉？这里就需要做下巧妙的变换了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center]

实际上`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的子数组的过程。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center 1]  
只要小了就右加，大了就左减，直到找到目标。

为什么尺取法是对的？我理解尺取法其实是解法二白银解法的一种优化，也是遍历了起点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分的答案，然后再想办法把分数提升上去，别最后交了白卷。** **给出一个可行解，然后再持续迭代优化，我觉得这也是解决一个复杂问题比较好的思路。**

最后送大家一句鸡汤，**没有人生下来就是王者，只是不断的努力成为了王者罢了。**

> 欢迎关注我的面试专栏[中高级程序猿面试题精选][Link 1]，**持续更新，永久免费**，本专栏会持续收录我遇到的中高级程序猿经典面试题，除了提供详尽的解题思路外，还会从面试官的角度提供扩展题，是大家面试进阶的不二之选，希望能帮助大家找到更好的工作。另外，也征集面试题，如果你遇到了不会的题 私信告诉我，有价值的题我会给你出一篇博客。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center]: /images/20210923/eee9c35be4694e0184eb08ca31321e2b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20210923/f675462dc41b4f9a9d8328d9c43ff461.png
[Link 1]: https://blog.csdn.net/xindoo/category_9991116.html