和至少为K的最短子数组

题目链接：https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/
描述

给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。
子数组 是数组中 连续 的一部分。

输入

1 <= nums.length <= 10^ 5
-10^ 5 <= nums[i] <= 10^ 5
1 <= k <= 10^ 9
例：nums = [2,-1,2], k = 3

输出

3

思路：
Ps:力扣昨日每一题再遇困难难度，过来水一发^ _ ^。
首先定义：
Sum(L ,R)为nums数组[L,R]的区间和
区间A在区间B左边：A.R 先考虑没有负数的情况：
由于数组中不存在负数，所以Sum(L+1 ,R)<=Sum(L ,R) （两个区间均合法）。因此我们可以先从0至n-1枚举R，然后再确定R对应的L，使得Sum(L ,R)刚好大于等于K（L==R或Sum(L+1 ,R)=K时才寻找对应的L。由于在计算过程中需要频繁的用到区间和，因此可以利用前缀和来进行快速计算（前缀和数组需要用long long 不然会溢出）。在寻找与R配对的L时从0开始枚举肯定是不行，可以根据Sum(L+1 ,R)<=Sum(L ,R)的特性，用二分查找来计算L。
最后考虑有负数的情况：
思路与没有负数时相同，只是要想办法把负数的影响去掉，仍能有Sum(L+1 ,R)<=Sum(L ,R)。
假设区间[Lj ,Rj]是nums数组中的一个负数区间(区间内均为负数)，若对于任何Lk∈[0 ,Lj],均满足Sum(Lk ,Rj)<=0，则该区间段不会出现在最短非空子数组中，即所求区间在[Lj ,Rj]的左边或右边。且最短子数组[L ,R]中nums[L]与nums[R]必为正整数，负数只会出现在中间。
因此我们将数组分成负数区间和非负区间，负数区间为[Lj ,Rj]，非负区间为[Li ,Ri]。对于负数区间[Lj ,Rj]，若它与左边若干连续区间合并后区间和大于0，则将这些区间向左合并为一个非负区间[Li, Rj]，并将Li原本的Ri保存为Mi（若[Li,Ri]已是合并区间则Mi不变）。例如nums=[2 ,-1 ,2]，有非负区间[0,0]、[2,2]，负区间[1,1]。[1,1]与[0,0]合并后为[0,1] ，Sum(0,1)=1>0，则仅剩非负区间为[0,1]（M=0）、[2,2]。若无论怎么合并都不能使区间和大于0则清掉该负数区间及其左边所有区间。例如nums[2,-1,2,-10,5]，有非负区间[0,0]、[2,2]、[4,4]，负数区间[1,1]、[3,3]。[1,1]可以向左合并成非负区间[0,1]，而[3,3]无法向左合并成非负区间，于是当选中[4,4]区间时其左边已经没有区间可供组合。
这样一来对于非负区间[Li ,Ri]，它左边的区间要么全是非负区间要么没有区间，若其左边原有的负数区间只有被合并为非负区间和被清除两种情况。若把区间看成一个数，则对于非负数nums[R]来说，它的左边全是非负数，因此有Sum(L(i+1) , R) 确定从左边哪个区间开始后就要找出从该区间哪个数开始到R的和刚好大于等于K。若Li正好与R在同一非负区间则直接二分找L即可。若Li在R左边的区间，这时就要用到负数区间向左合并时保存的Mi（Li与R不在同一区间时[Li ,Ri]必是合并过的区间，因为两个非负区间必有负数区间相隔），[Li ,Mi]内均为非负数且从合并时的规则可知Sum[Mi+1，Ri]<0，所以目标L必在[Li,Mi]中，二分查找即可。
主要思想是先确定负数区间[Lj, Rj]对答案[L ,R]的影响，然后依据影响将负数区间向左合并成非负区间或清除(清除时包括其左边所有区间)。通过这样的方式维护出非负区间，消除负数区间的影响，把问题简化为只有非负数时的情况。

const int Ms=1e5+5;
const int inf=0x3f3f3f3f;
int cnt[Ms];
long long sum[Ms];
struct node
{
    int l,r;
    int m;
    bool sgn;
}sec[Ms];
class Solution {
public:
    long long getsum(int l,int r)
    {
        if(l)return sum[r]-sum[l-1];
        else return sum[r];
    }
    int search(int l,int r,int R,int k)//二分找区间内的数
    {
         int m,ans=-1;
         while(l<=r)
         {
             m=(l+r)>>1;
             if(getsum(m,R)>=k)
             {
                 l=m+1;
                 ans=m;
             }
             else 
             {
                 r=m-1;
             }
         }
         return ans;
    }
    int search2(int l,int r,int R,int k)//二分找区间
    {
        int m,ans=-1;
        while(l<=r)
        {
            m=(l+r)>>1;
            if(getsum(sec[m].l,sec[R].r)>=k)
            {
                ans=m;
                l=m+1;
            }
            else
            {
                r=m-1;
            }
        }
        return ans;
    }
    int shortestSubarray(vector<int>& nums, int k) {
        int n=nums.size();
        int ans=inf,tmp,tot=0;
        sum[0]=nums[0];
        cnt[0]=1;
        sec[0].l=sec[0].r=0;
        sec[0].m=-1;
        sec[0].sgn=nums[0]>=0?1:0;
        if(nums[0]>=k)return 1;
        for(int i=1;i<n;i++)
        {
            sum[i]=sum[i-1]+nums[i];
            if(nums[i]>=0)
            {
                if(sec[tot].sgn)
                    sec[tot].r=i;
                else 
                {   
                    if(tot==0)tot=-1;
                    int pos=search2(0,tot-1,tot,1);//判断能否将该负数区间向左合并为非负区间
                    if(pos==-1)
                    {
                        tot=-1;
                    }
                    else 
                    {
                        if(sec[pos].m==-1)sec[pos].m=sec[pos].r;
                        sec[pos].r=sec[tot].r;
                        tot=pos;
                    }
                    sec[++tot]=(node){i,i,-1,1};
                }
            }
            else 
            {
                if(!sec[tot].sgn)
                {
                    sec[tot].r=i;
                }
                else 
                {
                    sec[++tot]=(node){i,i,-1,0};
                }
            }
            if(sec[tot].sgn)
            {
                if(getsum(sec[tot].l,sec[tot].r)>=k)
                {
                    tmp=search(sec[tot].l,sec[tot].r,sec[tot].r,k);
                    ans=min(i-tmp+1,ans);
                }
                else 
                {
                    long long  aim=k-getsum(sec[tot].l,sec[tot].r);
                    int pos=search2(0,tot-1,tot-1,aim);
                    if(sec[tot].r-sec[pos+1].l+1>=ans)
                        continue;
                    if(pos!=-1)
                    {
                        if(getsum(sec[pos].l,sec[tot-1].r)>=aim)
                        {
                            tmp=search(sec[pos].l,sec[pos].m,sec[tot-1].r,aim);
                            ans=min(i-tmp+1,ans);
                        }
                    } 
                }
            }
        }
        return ans==inf?-1:ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

若有什么错误，欢迎指正^ _ ^ 。