LeetCode 1658.将 x 减到 0 的最小操作数

乍一看到这题，马上想到的就是可以直接遍历对于固定的left，right应该在哪一个位置；然后进一步想到确定right位置可以用前缀和加二分查找；进而直接用前缀和遍历加查找即可。虽然过了但是时间空间复杂度都只超过20%的提交者，就去看了看题解的滑动窗口算法，这个名称之前在计网里有了解，但没想到还可以用在算法里。初始设定left=-1；right=0；如果当前sum小于x则right++；当前sum大于x则left++；right最大为n，跑一遍就可以把结果跑出来，确实实现上更好一些。

    int minOperations(vector<int>& nums, int x) {
        int n=nums.size(),ans=INT_MAX,t,l;
        vector<int> pre(n+1,0);
        for (int i=0;i<n;i++)
            pre[i+1]=nums[i]+pre[i];//转换成前缀和
        if (pre[n]<x) return -1;
        for (int r=0;r<=n;r++){
            t=x-pre[n]+pre[r];
            l=lower_bound(pre.begin(),pre.end(),t)-pre.begin();//stl的二分查找
            if (l<=n && pre[l]==t) ans=min(ans,n-r+l);
        }
        if (ans==INT_MAX) return -1;
        return ans;
    }

int minOperations(vector<int>& nums, int x) {
        int n=nums.size(),ans=INT_MAX,r=0;
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int lsum=0,rsum=sum;
        if (sum < x) return -1;
        for (int l=-1;l<n;l++){
            if (l!=-1){
                lsum+=nums[l];
            }
            while(r<n && lsum+rsum>x){
                rsum-=nums[r];
                r++;
            }
            if (lsum+rsum==x) ans=min(ans,(l+1)+(n-r));
        }
        if (ans==INT_MAX) return -1;
        return ans;
    }