江苏高校品牌专业建设网站,网站开发公司照片,网站设计的公司选哪家,广州翼讯资讯科技有限公司 网站个人主页#xff1a;Lei宝啊
愿所有美好如期而遇 本题链接
力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
输入描述
给定一个数组#xff0c;接口为int pivotIndex(vectorint nums)
输出描述
我们以示例1为例画图解释#xf… 个人主页Lei宝啊
愿所有美好如期而遇 本题链接
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
输入描述
给定一个数组接口为int pivotIndex(vectorint nums)
输出描述
我们以示例1为例画图解释 我们返回下标3。
算法分析
算法一暴力求解
直接遍历数组外层遍历到哪个i里层就遍历一次整个数组求和比较时间复杂度为O(N^2)这种时间复杂度我们不能接受。
算法二前缀和
方法一
我们创建dp表dp[i]表示从下标0到下标i的元素和用一个变量sum记录。
预处理dp表 使用dp表计算
接下来我们仍然是遍历数组但是我们需要提前计算出边界问题一个是0位置的边界一个是n-1位置的边界(这个边界在循环后判断)我们根据上图来判断一下0这个边界0的左边什么都没有题目使其和为0所以我们判断dp[n-1] - dp[0] 0就return 0否则继续我们的循环我们的循环从1开始到n-1边界结束然后判断这个边界即dp[n-2] 0我们return n-1; 否则就是没有找到这样的中间下标我们返回-1。 解题源码
class Solution
{
public:int pivotIndex(vectorint nums){int n nums.size();int sum 0;vectorint dp(n, 0);//dp[i]表示i位置及其前部分的和for (int i 0; i n; i){sum nums[i];dp[i] sum;}if (dp[n - 1] - dp[0] 0) return 0;for (int i 1; i n - 1; i){if (dp[i - 1] dp[n - 1] - dp[i]){return i;}}if (dp[n - 2] 0) return n - 1;return -1;}
};
方法二
我们创建前缀和dp表和后缀和dp表这里的dp[i]和我们方法一的含义是不同的这里的dp[i]意为下标0到下标i-1的和那么dp[i-1]意为下标0到下标i-2的和以此类推。
预处理dp表
前缀和是从前往后加后缀和是从后往前加什么意思呢我们看图 那么写成代码如何推导这两个dp表呢
dp[i]是下标0到下标i-1的和dp[i-1]是下标0到下标i-2元素的和......,dp[1]就是dp[0]加上下标为0元素的值dp[0]我们初始化为0。因为题目规定下标为0或者右边的边界时左边元素和右边元素和为0所以我们dp[0],dp[n-1]初始化为0。
我们写成公式就是
前缀 dp[i] dp[i-1] nums[i-1]i从1开始后缀 dp[i] dp[i1] nums[i1]i从n-2开始
使用dp表计算
我们使前缀dp[i] 与 后缀dp[i]做比较相等则返回下标循环外则返回-1。
解题源码
class Solution
{
public:int pivotIndex(vectorint nums){int n nums.size();vectorint f(n, 0);vectorint g(n, 0);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;}
};
其实博主个人感觉方法一好理解一点不过方法二的思想值得我们去学习同时不要死记前缀和后缀和公式dp[i]的情况是不同的就像我们的方法一和方法二他们中的dp[i]含义就不同我们需要理解的是思想。
