从双方问题中选择,两种实现都做同样的事情但是一个被接受而另一个不被接受,为什么?

问题描述 投票:0回答:0

问题链接:https://www.interviewbit.com/problems/pick-from-both-sides/

我正在使用滑动窗口来解决它,方法是找到最小的连续总和子数组,然后从 totalSum 中减去它。

这会被接受:

int Solution::solve(vector<int> &A, int B) {
int n=A.size();
int totalSum=0, sum=0, minn;
for(int i=0; i<A.size(); i++) totalSum+=A[i];
int ws=0, we=n-B-1;
for(int i=ws; i<=we; i++) sum+=A[i];
minn=sum;
ws++;we++;
while(we < n) {
    sum+=(A[we]-A[ws-1]);
    minn=min(minn, sum);
    ws++; we++;
}
return totalSum-minn;
}

这不是为什么?(在硬测试用例上给出错误的答案)

int Solution::solve(vector<int> &A, int B) {
int n=A.size();
int totalSum=0, sum=0, minn;
for(int i=0; i<A.size(); i++) totalSum+=A[i];
int ws=0, k=n-B-1;
minn = INT_MAX;
for(int we=ws; we<n; we++) {
    sum+=A[we];
    if(we>=k) {
        minn=min(minn, sum);
        sum-=A[ws];
        ws++;
    }
}
return totalSum-minn;
}

如何修复第二个实现?

c++ arrays sliding-window
© www.soinside.com 2019 - 2024. All rights reserved.