当前位置：网站首页>和为s的连续正数序列

和为s的连续正数序列

2022-08-11 10:35:00 【51CTO】

和为s的连续正数序列_双端队列

参考链接： https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/solution/shi-yao-shi-hua-dong-chuang-kou-yi-ji-ru-he-yong-h/

滑动窗口

       
       class 
       
       Solution {
       
       public:
       
       vector
       
       <
       
       vector
       
       <
       
       int
       
       >> 
       
       findContinuousSequence(
       
       int 
       
       target) {
       
       //滑动窗口，L为左边界，R为右边界[L,R]
       
       //L、R 只会往右滑动，
       
       vector
       
       <
       
       vector
       
       <
       
       int
       
       >>
       
       res;
       
       //题意可知从大于等于1开始
       
       int 
       
       L
       
       =
       
       1,
       
       R
       
       =
       
       1;
       
       int 
       
       sum
       
       =
       
       L;
       
       //因为是连续的正数序列，L最多到target/2 ，因为至少含有两个数，超过target/2 ，则必然会大于target
       
       while(
       
       L
       
       <= 
       
       target
       
       /
       
       2)
       
    {
       
       if(
       
       sum
       
       ==
       
       target)
       
       //L往右滑动
       
        {
       
       vector
       
       <
       
       int
       
       >
       
       tmp;
       
       for(
       
       int 
       
       i
       
       =
       
       L;
       
       i
       
       <=
       
       R;
       
       i
       
       ++)
       
       tmp.
       
       push_back(
       
       i);
       
       res.
       
       push_back(
       
       tmp);
       
       //找到值之后也需要维护
       
       sum
       
       -=
       
       L;
       
       L
       
       ++;
       
        }  
       
       else 
       
       if(
       
       sum
       
       <
       
       target)
       
       //R往右滑动，
       
        {
       
       R
       
       ++;
       
       sum
       
       +=
       
       R;    
       
        }
       
       else 
       
       if(
       
       sum
       
       >
       
       target)
       
       //L往右滑动，
       
        {
       
       sum
       
       -=
       
       L;
       
       L
       
       ++; 
       
        }
       
    }
       
       return 
       
       res;
       
}
       
};
      
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.

滑动窗口+双端队列

       
       class 
       
       Solution {
       
       public:
       
       vector
       
       <
       
       vector
       
       <
       
       int
       
       >> 
       
       findContinuousSequence(
       
       int 
       
       target) {
       
       //滑动窗口，L为左边界，R为右边界[L,R]
       
       //L、R 只会往右滑动，
       
       vector
       
       <
       
       vector
       
       <
       
       int
       
       >>
       
       res;
       
       //双端队列维护此时的滑动窗口
       
       deque
       
       <
       
       int
       
       >
       
       record;
       
       //题意可知从大于等于1开始
       
       int 
       
       L
       
       =
       
       1,
       
       R
       
       =
       
       1;
       
       int 
       
       sum
       
       =
       
       L;
       
       record.
       
       push_back(
       
       L);
       
       //因为是连续的正数序列，L最多到target/2 ，因为至少含有两个数，超过target/2 ，则必然会大于target
       
       while(
       
       L
       
       <= 
       
       target
       
       /
       
       2)
       
    {
       
       if(
       
       sum
       
       ==
       
       target)
       
       //L往右滑动
       
        {
       
       vector
       
       <
       
       int
       
       >
       
       tmp(
       
       record.
       
       begin(),
       
       record.
       
       end());
       
       res.
       
       push_back(
       
       tmp);
       
       //找到值之后也需要维护
       
       sum
       
       -=
       
       L;
       
       L
       
       ++;
       
       record.
       
       pop_front();
       
        }
       
       else 
       
       if(
       
       sum
       
       <
       
       target)
       
       //R往右滑动，
       
        {
       
       R
       
       ++;
       
       record.
       
       push_back(
       
       R);
       
       sum
       
       +=
       
       R;    
       
        }
       
       else 
       
       if(
       
       sum
       
       >
       
       target)
       
       //L往右滑动，
       
        {
       
       sum
       
       -=
       
       L;
       
       record.
       
       pop_front();
       
       L
       
       ++; 
       
        }
       
    }
       
       return 
       
       res;
       
}
       
};
      
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.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_14508933/5566122

当前位置：网站首页>和为s的连续正数序列

和为s的连续正数序列

边栏推荐

猜你喜欢

随机推荐