前缀和：中心下标与数组乘积

文章目录一、左右信息的统一视角二、寻找数组的中心下标三、除了自身以外数组的乘积一、左右信息的统一视角对于下标i可以把数组拆成三部分[0, i) nums[i] (i, n)中心下标比较左右两侧的和除自身以外数组的乘积则把左右两侧的乘积相乘。两题的共同点是都不需要在处理每个i时重新扫描左右区间。二、寻找数组的中心下标LeetCode 724. 寻找数组的中心下标设dp[i]表示下标i左侧所有元素的和那么dp[nums.length]就是整个数组的总和。如果i是中心下标则有左侧和 右侧和 dp[i] dp[nums.length] - dp[i] - nums[i]移项后可以直接判断dp[i] * 2 nums[i] dp[nums.length]这样只需要一个前缀和数组不必再建立后缀和数组。代码从左向右检查因此找到的第一个结果自然是最靠左的中心下标。classSolution{publicintpivotIndex(int[]nums){long[]dpnewlong[nums.length1];for(inti1;inums.length1;i){dp[i]dp[i-1]nums[i-1];}for(inti0;inums.length;i){if(dp[i]*2nums[i]dp[nums.length]){returni;}}return-1;}}时间复杂度为O(n)空间复杂度为O(n)。按照本题约束int足以保存总和这里使用long可以降低代码对数值范围的依赖。三、除了自身以外数组的乘积LeetCode 238. 除了自身以外数组的乘积如果先求全部元素的乘积再除以nums[i]遇到0时就无法处理而且题目本身也要求不使用除法。可以分别保存左侧前缀积和右侧后缀积dpleft[i]下标0到i - 1的元素乘积dpright[i]下标i到len - 1的元素乘积。因此下标i的答案为ret[i] dpleft[i] * dpright[i 1]数组两端没有元素的一侧按乘法单位元1处理所以初始化dpleft[0] 1、dpright[len] 1。classSolution{publicint[]productExceptSelf(int[]nums){intlennums.length;int[]dpleftnewint[len1];int[]dprightnewint[len1];dpleft[0]1;dpright[len]1;for(inti0;ilen;i){dpleft[i1]dpleft[i]*nums[i];}for(intilen-1;i0;i--){dpright[i]dpright[i1]*nums[i];}int[]retnewint[len];for(inti0;ilen;i){ret[i]dpleft[i]*dpright[i1];}returnret;}}题目保证相关前缀积、后缀积与答案都在 32 位整数范围内因此可以使用int[]。时间复杂度为O(n)额外空间复杂度为O(n)。