滴滴笔试-区间最小值

目录

1. 输入
2. 输出
3. 样例

题目描述

给出一个长度为 n 的数组 a，你需要在这个数组中找到一个长度至少为 m 的区间，使得这个区间内的数字的和尽可能小。

输入

第一行包含两个正整数 n，m，表示数组的大小和所选取间的最小长度。（1 ≤ n < 100000），第二行包含 n 个整数，中间用空格隔开 0 ≤ |ai| ≤ 1000。

输出

输出仅包含一个整数，表示所选取间的和。

样例

输入1

5 3
1 2 3 4 5

输出1

6

输入2

5 3
-2 1 -1 -1 -1

输出2

-4

AC代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int min, sum = 0;
        int []a = new int[n];
        int []dp = new int[n];
        for (int i = 0; i < n; i++) 
            a[i] = sc.nextInt();
        for (int i = 0; i < m; i++) 
            sum += a[i];
        min = sum;
        if (m == 0) {
            dp[0] = a[0];
            m = 1;
            sum = a[0];
        }
        else 
            dp[m-1] = sum;
        
        for (int i = m; i < n; i++) {
            sum += a[i] - a[i-m];
            dp[i] = Math.min(sum, dp[i-1] + a[i]);
            min = Math.min(min, dp[i]);
        }
        System.out.println(min);
    }
}

这个题目有个坑，就是 m 可能为 0。如果不存在 m 为 0 的情况代码可以更简洁：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int []a = new int[n];
        int []dp = new int[n];
        for (int i = 0; i < n; i++) 
            a[i] = sc.nextInt();
        int sum = 0;
        for (int i = 0; i < m; i++) 
            sum += a[i];
        int min = sum;
        dp[m-1] = sum;
        for (int i = m; i < n; i++) {
            sum += a[i] - a[i-m];
            dp[i] = Math.min(sum, dp[i-1] + a[i]);
            min = Math.min(min, dp[i]);
        }
        System.out.println(min);
    }
}

而且题目里说是至少长度为 m。我第一次读题读成了长度是 m。所以代码是：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int []a = new int[n];
        for (int i = 0; i < n; i++) 
            a[i] = sc.nextInt();
        int sum = 0;
        for (int i = 0; i < m; i++) 
            sum += a[i];
        int min = sum;
        for (int i = m; i < n; i++) {
            sum += a[i] - a[i-m];
            min = Math.min(min, sum);
        }
        System.out.println(min);
    }
}

发现样例 2 过不了，还没发现问题，以为是数组可以首尾衔接，选择首尾两端的数字，代码又改成了（就是添加了 19 ~ 22行）：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int []a = new int[n];
        for (int i = 0; i < n; i++) 
            a[i] = sc.nextInt();
        int sum = 0;
        for (int i = 0; i < m; i++) 
            sum += a[i];
        int min = sum;
        for (int i = m; i < n; i++) {
            sum += a[i] - a[i-m];
            min = Math.min(min, sum);
        }
        for (int i = 0; i < m; i++) {
            sum += a[i] - a[n-m+i];
            min = Math.min(min, sum);
        }
        System.out.println(min);
    }
}

所以这个题交了 3 次才过的