前缀和+二分答案 or 尺取法：子序列问题III

柔光的暖阳◎ 2023-10-06 19:40 30阅读 0赞

## 前缀和+二分答案：子序列问题III ##

#### 文章目录 ####

*  前缀和+二分答案：子序列问题III
 *   *   *  前缀和
         *  二分答案
         *   *  二分答案模板
         *  问题：
         *  思路（前缀和 + 二分答案）：
         *  代码：
         *  思路（尺取法）：
         *  代码：

#### 前缀和 ####

前缀和是一种重要的预处理，能大大降低查询的时间复杂度。前缀和是指一个数组的某项下标之前(包括此项元素)的所有数组元素的和。即我们可以用一个数组来保存另一个数组的前缀和，记为前缀和数组：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]  
  利用空间换时间的思想，通过建立前缀和数组，我们可以将求数组中某个连续序列之和的操作从O(n)的复杂度降到O(1)  
  例如我们有一个具有10个元素的数组A，设下标从1开始，pre\[8\]即为数组A的前8项之和，即A\[1\] + A\[2\] + A\[3\] + … + A\[8\]。pre\[3\]为A\[1\] + A\[2\] + A\[3\]。我们若想得到数组的4 ~ 8位之和，只需将pre\[8\] - pre\[3\]即可  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]

#### 二分答案 ####

对于一些问题，我们可能有一个答案的可能范围，例如数组的连续序列的长度为1 ~ n(n为数组长度)，我们可以遍历所有情况，这需要O(n)，若满足条件的答案单调，则我们可以使用二分答案的方法将枚举答案过程的复杂度降为O(logn)。  
  二分答案即在答案可能的范围内\[L,R\]二分查找答案，检查当前答案是否满足题目的条件要求，根据判断结果更新查找区间。二分答案要求满足条件的答案单调。  
  二分答案一般用于求解满足某种条件下的最大（小）值问题，可能解决的问题有：

*  求最大的最小值
 *  求最小的最大值
 *  求满足条件下的最小（大）值
 *  求最靠近一个值的值
 *  求最小的能满足条件的代价

##### 二分答案模板 #####

// 变量初值
            int l = 下界, r = 上界, mid;
            
            // 当需要找到一个尽可能小的答案时
            while (l < r) {
        
                // (l + r) / 2为向下取整
                mid = (l + r) / 2;
                if (check(mid)) {
        
                    // mid满足条件
                    r = mid;
                } else {
        
                    // mid不满足条件
                    l = mid + 1;
                }
            }
    
            // 当需要找到一个尽可能大的答案时
            while (l < r) {
        
                // (l + r + 1) / 2为向上取整
                mid = (l + r + 1) / 2;
                if (check(mid)) {
        
                    // mid满足条件
                    l = mid;
                } else {
        
                    // mid不满足条件
                    r = mid - 1;
                }
            }
            
            // 返回l或r均可，因为最后l == r
            return l;

当需要找到尽可能小的答案时，mid = (l + r) / 2，(l + r) / 2为向下取整，例如当l = 2, r = 3, (l + r) / 2 = 2。我们将尽可能小的尝试赋给mid，若不使用向下取整，上述情况会造成死循环。当mid满足条件时，我们将mid赋给r，l和r指示的都是满足条件的值，当mid不满足条件时，我们将mid + 1赋给l。若要找尽可能大的答案，分析同理，注意此时mid = (l + r + 1) / 2，(l + r + 1) / 2为向上取整，例如当l = 2, r = 3, (l + r + 1) / 2 = 3。最后返回l或r均可，在while循环结束后，l一定等于r，也即我们要找的答案。

#### 问题： ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 3]

#### 思路（前缀和 + 二分答案）： ####

对于该题，有一个很显然但错误的想法，从小到大枚举区间长度，然后遍历序列求出该长度下的所有区间和，看是否有>=S的。但是复杂度过高，N为1e5级别，O(N^3)显然不行。我们需要优化时间复杂度。  
  我们可以使用前缀和，将O(N ^ 3)优化为O(N ^ 2)，可是这样复杂度依然是O(N ^ 2)。当问题的规模达到1e5时，O(N ^ 2)的算法已经不再适用，因此除开前缀和，我们还需要使用二分答案，将O(N ^ 2)进一步优化到O(NlogN)  
  注意一个事实：当我们枚举到一个区间长度len，存在一个长为len的区间和>=S,说明了：

*  （1）len可以作为备选答案。
 *  （2）所有大于len的长度无需再枚举。答案肯定在小于等于len的范围内。为什么呢？  
      因为所有的数都是正整数，一定存在一个长len+1,len+2,len+3……的区间和>=S，题目又要我们选最小的，故比len大的长度都无需再枚举。

根据上述分析，答案有单调性，满足二分答案的使用条件

对于该题，连续序列的长度为1 ~ n(n为数组长度)，因此我们可以使用二分答案枚举序列长度，然后用一个循环枚举序列的起始点，使用前缀和判断序列和是否大于等于s。若大于等于，则表示该长度满足条件，即存在长为mid的区间和>=S，因此我们将mid赋给r，若小于，则所有长度<=mid的区间均不满足题意，答案一定在长度>mid的区间中，将mid + 1赋给l

**需注意的点：**

*  若数组总和小于s，即pre\[n\] (n为数组长度) < s，则输出0，不可能存在答案
 *  使用二分模板，枚举序列起始点的循环放在check函数中

#### 代码： ####

import java.util.*;
    
    public class Main {
        
        static long[] pre = new long[100002];
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            int n, i, l, r, mid;
            long s;
            while (scanner.hasNextInt()) {
        
                n = scanner.nextInt();
                s = scanner.nextLong();
                pre[0] = 0;
                for (i = 1;i <= n;i++) {
        
                    pre[i] = pre[i - 1] + scanner.nextInt();
                }
                l = 1;
                r = n;
                while (l < r) {
        
                    mid = (l + r) / 2;
                    if (check(mid, n, s)) {
        
                        r = mid;
                    } else {
        
                        l = mid + 1;
                    }
                }
                if (pre[n] < s) {
        
                    System.out.println(0);
                } else {
        
                    System.out.println(l);
                }
            }
        }
    
        static boolean check(int m, int n, long s) {
        
            int i;
            for (i = 1;i + m - 1 <= n;i++) {
        
                if (pre[i + m - 1] - pre[i - 1] >= s) {
        
                    return true;
                }
            }
            return false;
        }
    }

#### 思路（尺取法）： ####

尺取法也可称为双指针法，尺取法一般用于解决具有单调性的区间问题。一般能用尺取法做的题用二分也能做，二分只需要有单调性，但尺取法只能解决单调性区间问题，因此它的适用范围更小  
  对于本题，我们设连续子序列的左端点为l，右端点为r。首先l=1，r=1。然后不断增加r，相当于把所求连续子序列的右端点往右延伸，当延伸到S<=sum\[l,r\]的区间时，我们这个时候已经出现了一个满足条件的解。因为题目要求最短的连续子序列长度，所以继续延伸r是得不到更优的解的。所以此时我们把r停下来，然后开始使l加一，让l追上去一位。如果l延伸了之后，我们的\[l,r\]区间和还是大于等于S的，那么我们更新答案，继续延伸l；否则，停止延伸l，又开始重新延伸r。就这样不断重复地移动r，移动l，移动r，移动l。直到r指针移动到尽头，我们就把所有的满足条件的连续子序列枚举完毕了。因为l和r指针一直向右移动，并没有回溯，所以时间复杂度为O(n)。  
  尺取法即为该题的最优解

#### 代码： ####

import java.util.*;
    
    public class Main {
        
        static int[] array = new int[100005];
        public static void main(String[] args) {
        
            int n, S, i, ans, l, r, sum;
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNextInt()) {
        
                ans = 100005;
                n = scanner.nextInt();
                S = scanner.nextInt();
                for (i = 0; i < n; i++) {
        
                    array[i] = scanner.nextInt();
                }
                l = 0;
                r = 0;
                sum = array[0];
                while (r < n && l <= r) {
        
                    while (sum < S && r < n - 1) {
        
                        r++;
                        sum += array[r];
                    }
                    if (sum >= S) {
        
                        ans = Math.min(ans, r - l + 1);
                    }
                    sum -= array[l];
                    l++;
                }
                System.out.println(ans == 100005 ? 0 : ans);
            }
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/53f47ee7aa894da3b65b9890a9a24a97.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/e64afad1933f44b0a615eef7c30d7848.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/ad1dc2006ae44c1c8074d7a2ded691f0.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/0d63833911b44029b37522516694e02a.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16