日野弥生：勉強しよう
LeetCode 1991 - 找到数组的中间位置
发表于2024年12月05日
时隔多年，重开了新的开发人生。以做leetcode题目起步。没看到前缀和的字眼，直接按照自己的理解写了一份解答,需要一次遍历，数组头和尾需要做边界检查。
class Solution {
public:
int pivotIndex(vector<int>& nums) {
int sum_behind = 0, sum_after = 0;
if(nums.empty())
return -1;
if(nums.size() == 1)
return 0;
for(auto iter: nums)
{
sum_after+= iter;
}
sum_after = sum_after - nums[0];
for(int i =0;i<nums.size();i++)
{
if(sum_after == sum_behind)
return i;
int size = nums.size();
if(i < size -1)
{
sum_behind +=nums[i];
sum_after -= nums[i+1];
}
}
return -1;
}
};看了评论后，发现可以通过简单的数学算法实现来规避一些边界检查。
class Solution {
public:
int findMiddleIndex(vector<int>& nums) {
int sum = 0,sum_before=0;
for(auto iter:nums)
{
sum+= iter;
}
for(int i=0;i<nums.size();i++)
{
sum_before+=nums[i];
if(sum_before*2 -nums[i] == sum)
return i;
}
return -1;
}
};看了官方题解答案，发现两个for循环其实可以并成一个，且运用了前缀和这种算法思想。