当前位置: 首页 > news >正文

算法:724.寻找数组的中心下标

题目

链接:leetcode链接

在这里插入图片描述


思路分析(前缀和)

根据题意,我们可以将数组看成三个部分
[left] [mid] [right]
我们只需要[left]区间内的元素和等于[right]区间的元素和即可,此时mid就是中心下标
那么我们可以借助前缀和思想,将[left]区间和[right]区间的元素和求出来,就可以很好的方便比较

注意,前缀和算法不仅仅是一种算法,更是一种思想。

看到这里,读者们可能会问,通过前缀和算法为什么可以求出[right]区间的和呢?
当然,用整个数组的和减去[left]区间和mid元素可以得到答案,
但是,这里介绍一种更好的办法
采用后缀和算法,
什么是后缀和算法呢?
顾名思义,将前缀和反过来,我们从数组末尾向前求和就成了后缀和

具象到代码上就是
f----前缀和
g—后缀和

f[i] = f[i-1] + nums[i-1] 注意,这里是nums[i-1]不是nums[i],是因为求的是mid前,不包括mid
g[i] = g[i+1] + nums[i+1]

最后处理好前缀和数组和后缀和数组之后,只需要遍历比较前缀和数组和后缀和数组即可。


代码

int pivotIndex(vector<int>& nums) {int n = nums.size();vector<int> f(n);vector<int> g(n);for(int i = 1;i< n;++i)f[i] = f[i-1] + nums[i-1];for(int i = n-2;i>=0;--i)g[i] = g[i+1] + nums[i+1];for(int i = 0;i < n;++i){if(f[i] == g[i])return i;}return -1;}

http://www.mrgr.cn/news/45783.html

相关文章:

  • 面试(十)
  • 【JVM】内存分析工具JConsole/Visual VM
  • 每日OJ题_牛客_平方数_数学_C++_Java
  • 面试题:Redis(一)
  • 回到原点再出发
  • 职场上的人情世故,你知多少?这五点一定要了解
  • Python获取json返回的字符串获取方法大全
  • 若依初相识
  • 每天一道面试题5——Linux内核包含哪些部分?
  • 【C语言刷力扣】1678.设计Goal解析器
  • Python酷库之旅-第三方库Pandas(137)
  • 解决方案:Pandas里面的loc跟iloc,有什么区别
  • 形式逻辑 | 管理类联考
  • 初入网络学习第一篇
  • Spring Validation —— 参数校验框架
  • 媒界:家庭出行不用愁 江铃集团新能源易至EV3青春版值得拥有
  • C语言基础之结构体
  • 一分钟掌握 Java22 新特性
  • ant-design为input设置默认值,form失效
  • 如何在 MySQL 中处理 BLOB 和 CLOB 数据类型