最近，一个好久没联系的老同学突然给我吐槽，天天在实验室里给老板打工，没时间刷题。这不刚刚面试完一家大厂，就被秀的体无完肤！面对老同学的抱怨，我深有体会！
在这里，温馨提醒一下，将要找工作的同学们，有空一定要多补补 算法与数据结构 。避免掉入 “一看就会，一写就凉" 的陷阱，打破 “只会暴力求解，不会衡量复杂度” 的尴尬局面！
废话就不多说了，下面进入正题！（PS：下面以张三指代老同学）
首先进去是一分钟的自我介绍，接着就进入了 “手撕代码” 环节。还没等张三反应过来，一道题目就迎面而来。
题目大概是这样的：
看完题目后，张三窃喜（心想这么简单的题，还能难住我？）。说时迟，那时快！没用几分钟，就一顿写完了。
张三：面试官，我写完了，您看一下！（脸上洋溢着得意的表情~）
面试官：好的，我看看~
内容是这样的：
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
}
};
看完之后，面试官脸色有点凝重。。
面试官：再仔细看一下题，你觉得需要单独开辟一个空间去存储结果吗？
张三：恩。。可能不需要，我再想想！（一边摸着头脑，一边打量着题目）
知道问题后，张三马上将程序进行了优化，内容是下面这样：
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)，你能再优化一下吗？
张三又看了看题目，没有什么思路。
张三恍然大悟，连忙说：谢谢指导，我想我应该有办法了！
于是不一会儿功夫，再次将代码进行了优化，最终结果如下：
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;
}
};
看完之后，面试官才露出了微微的笑容~
当然，这可能也不是最优解。优秀的你们，如果有更好的解法，可以在评论区留言！
相关文章推荐