【C语言】每日一题（寻找数组的中心下标）

寻找数组的中心下标，链接奉上

暴力循环

​​​​​​​思路：

依旧是我们的老朋友，暴力循环。
1.可以利用外层for循环，循环变量为数组下标，在循环内分别求出下标左边与右边的sum
2.在边界时讨论，
当下标为左边界（nums[0]）时，left sum=0；当下标为右边界（nums[numsSize-1）时，right sum=0
3.讨论完特殊情况后，进行左边与右边的比较；
左==右时，即代表我们找到了下标；
否则返回-1。

代码实现：

int pivotIndex(int* nums, int numsSize)
{for(int i=0;i<numsSize;i++)//外层for循环{int Lsum=0;//left sum的缩写。//在循环内部放置是因为防止这次的lsum加上上次的lsum，造成计算错误。if(i==0)//特殊情况，左边界Lsum=0;elsefor(int j=0;j<i;j++)//求lsum的值Lsum+=nums[j];int Rsum=0;if(i==numsSize-1)Rsum=0;elsefor(int j=i+1;j<numsSize;j++)Rsum+=nums[j];if(Lsum==Rsum)return i;}return -1;
}

但是，此种方法的时间复杂度巨大无比，我们可以进行改进

我们发现，每次进入for循环内时，总是会有重复的计算出现，比如：
计算i=0时的Rsum（ringt sum缩写），每次都重新计算了一遍，但是我们可以在上一次的基础上进行减nums[i]，大大降低了计算量。

代码实现：

int pivotIndex(int* nums, int numsSize)
{int i=0;int j=0;int Lsum=0;int Rsum=0;for(i=0;i<numsSize;i++)//首先计算出Rsum的值，i=0时{Rsum+=nums[i];}for(i=0;i<numsSize;i++){if(i==0)Lsum=0;elseLsum+=nums[i-1];//上一次的基础上加上nums[i-1]if(i==numsSize-1)Rsum=0;elseRsum-=nums[i];//上一次的基础上减上nums[i]if(Lsum==Rsum)return i;}return -1;
}

但是这样每次进循环都会判断一次是否在边界处
则可以在外部进行判断

int pivotIndex(int* nums, int numsSize)
{int i=0;int j=0;int Lsum=0;int Rsum=0;for(i=1;i<numsSize;i++)Rsum+=nums[i];if(Lsum==Rsum)return 0;for(i=1;i<numsSize;i++){Lsum+=nums[i-1];Rsum-=nums[i];if(Lsum==Rsum)return i;}return -1;
}

前缀和

思路：

当找到下标时，意味着左右元素和相等。
设数组和为total，则total==Rsum+Lsum+nums[i]
又因左右相等，故total=＝2Rsum+nums[i]

代码实现：

int pivotIndex(int* nums, int numsSize)
{int total=0;int Rsum=0;for(int i=0;i<numsSize;i++){total+=nums[i];}for(int i=0;i<numsSize;i++){if(Rsum*2+nums[i]==total)return i;Rsum+=nums[i];}return -1;
}

欢迎讨论哦