阿里面试官：不会衡量复杂度的程序员，我们不需要！

比眉伴天荒 2022-11-30 05:48 28阅读 0赞

> 写在前面：大家好！我是【AI 菌】，一枚爱弹吉他的程序员。我`热爱AI、热爱分享、热爱开源`！ 这博客是我对学习的一点总结与思考。如果您也对 `深度学习、机器视觉、算法、Python、C++` 感兴趣，可以关注我的动态，我们一起学习，一起进步~  
> 我的博客地址是：[【AI 菌】的博客][AI]  
> 我的项目地址是：[【AI 菌】的 GitHub][AI _ GitHub]

最近，一个好久没联系的老同学突然给我吐槽，天天在实验室里**给老板打工，没时间刷题**。这不刚刚面试完一家大厂，就被秀的体无完肤！面对老同学的抱怨，我深有体会！

![在这里插入图片描述][2020082323593476.jpg_pic_center]  
在这里，温馨提醒一下，将要找工作的同学们，有空一定要多补补 **算法与数据结构** 。避免掉入 **“一看就会，一写就凉"** 的陷阱，打破 **“只会暴力求解，不会衡量复杂度”** 的尴尬局面！

废话就不多说了，下面进入正题！（PS：下面以**张三**指代老同学）

--------------------

首先进去是一分钟的自我介绍，接着就进入了 **“手撕代码”** 环节。还没等张三反应过来，一道题目就迎面而来。

题目大概是这样的：

> 给定一个整数类型的数组 nums，要求编写一个能够返回数组 “**中心索引**” 的方法。  
> 数组的 中心索引 是这样定义的：数组中心索引的左侧所有元素相加的和 = 右侧所有元素相加的和。  
> 如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。

看完题目后，张三窃喜（心想这么简单的题，还能难住我？）。说时迟，那时快！没用几分钟，就一顿写完了。

**张三**：面试官，我写完了，您看一下！（脸上洋溢着得意的表情~）

**面试官**：好的，我看看~

内容是这样的：

class Solution { 
    public:
        int pivotIndex(vector<int>& nums) { 
        	vector<int> result;  //存放所有可能的中心索引
        	int flag = 0; //标志位：存在中心索引置1，否则置0
            for(int i=0; i<nums.size(); i++){ 
                long sum1=0, sum2=0;  //初始化元素左边总和、右边总和
                //计算左边总和
                for(int j=0; j<i; j++)
                    sum1+=nums[j];
                //计算右边总和
                for(int k=i+1; k<nums.size(); k++)
                    sum2+=nums[k];
                //如果相等，则索引i是中心索引 
                if(sum1==sum2){ 
                    result.push_back(i);
                    flag = 1 //存在中心索引，标志位置1
                }
            }
            if(flag)
            	return result[0];//如果存在中心索引，则返回最靠近左边的那个索引
            else
            	return -1；//不存在中心索引，那么返回 -1
        }
    };

看完之后，面试官脸色有点凝重。。

**面试官**：再仔细看一下题，你觉得需要单独开辟一个空间去存储结果吗？

**张三**：恩。。可能不需要，我再想想！（一边摸着头脑，一边打量着题目）

> 果然，题目没理解清楚！**题目要求，如果存在多个中心索引，那么只需要返回最靠近左边的那一个就可以了。** 这说明，当我们从左向右去遍历数组时，只要找到第一个满足条件的中心索引就可以了；而不用单独声明一个vector去存储结果，这样无疑会增加代码的**空间复杂度**！（特别是当满足条件的中心索引很多时）

知道问题后，张三马上将程序进行了优化，内容是下面这样：

class Solution { 
    public:
        int pivotIndex(vector<int>& nums) { 
            for(int i=0; i<nums.size(); i++){ 
            	//初始化
                int sum1=0,sum2=0;
                //计算左边元素总和
                for(int j=0; j<i; j++)
                    sum1+=nums[j];
                //计算右边元素总和
                for(int k=i+1; k<nums.size(); k++)
                    sum2+=nums[k];
                if(sum1==sum2){ 
                    return i;  //返回中心索引
                }
            }
            return -1; //不存在中心索引，则返回-1
        }
    };

面试官看完后，表情终于松弛了下来。但是对这个结果还是不太满意！

**面试官：** 你的这种方法，空间复杂度是 O ( 1 ) O(1) O(1)，但是时间复杂度是 O ( n 2 ) O(n^2) O(n2)，你能再优化一下吗？

**张三**又看了看题目，没有什么思路。

> 面试官似乎看出了他的窘境，接着说：你从左往右去遍历这个数组，针对每一个索引 i，你都会采用嵌套for的方式去计算该元素左边的元素之和sum1、以及右边元素之和sum2。**这样做虽然简单，但是每一个都要重新计算sum1和sum2，无疑增加算法的时间复杂度！**

**张三**恍然大悟，连忙说：谢谢指导，我想我应该有办法了！

于是不一会儿功夫，再次将代码进行了优化，最终结果如下：

class Solution { 
    public:
        int pivotIndex(vector<int>& nums) { 
            int sum=0, sum1=0, sum2=0;
            //计算数组总和
            for(int i=0; i<nums.size(); i++)
                sum += nums[i]; 
            //寻找第一个中心索引
            for(int i=0; i<nums.size(); i++){ 
                sum2 = sum - nums[i] - sum1; //右边累计和
                if(sum1==sum2)
                    return i;
                sum1 += nums[i]; //左边累计和
            }
            return -1;
        }
    };

看完之后，面试官才露出了微微的笑容~

> 这种方法确实妙，实现了时间复杂度 O ( n ) O(n) O(n)，空间复杂度 O ( 1 ) O(1) O(1)。

> 改进之处在于，求sum1和sum2的方式。原来是通过嵌套for的方式，无疑使得时间复杂度多了一个数量级！  
> 现在直接通过每次累加计算得sum1，然后sum2 = 数组总和sum - 当前元素nums\[i\] - 左边总和sum1，通过减法即可实现。总体来说，只用了两个串联的for循环，所以最终的时间复杂度是 O ( n ) O(n) O(n)。

**当然，这可能也不是最优解。优秀的你们，如果有更好的解法，可以在评论区留言！**

--------------------

***相关文章推荐***

[算法与数据结构专栏：从小白到入门，从人门到入坑！][Link 1]

[AI]: https://blog.csdn.net/wjinjie
[AI _ GitHub]: https://github.com/Keyird/DeepLearning-TensorFlow2.0
[2020082323593476.jpg_pic_center]: /images/20221124/e308b735c2f0433c820e933ef34dc7c2.png
[Link 1]: https://blog.csdn.net/wjinjie/category_9880426.html