算法题：数组连续和

题目描述

给定一个含有 $N$ 个正整数的数组，求出有多少个连续区间（包括单个正整数），它们的和大于等于 $x$ 。

输入描述

第一行两个整数 $N, x$ ( $0 < N \le 100000, 0 \le x \le 10000000$ )。
第二行有 $N$ 个正整数（每个正整数小于等于 100）。

输出描述

输出一个整数，表示所求的个数。

示例 1

输入

3 7
3 4 7

输出

说明
满足条件的连续区间有 4 个，分别是：

`` (和为 7)
`` (和为 11)
`` (和为 14)
`` (和为 7)

示例 2

输入

10 10000000
1 2 3 4 5 6 7 8 9 10

输出

说明
所有元素的总和远小于 10000000，因此没有满足条件的区间。

💡 解题思路与代码优化

您提供的原始代码使用了双重循环，时间复杂度为 $O(N^2)$ 。考虑到 $N$ 的最大值为 100,000， $N^2$ 将达到 $10^{10}$ 级别，这在大多数在线判题系统中会导致“运行超时”。

优化方案：滑动窗口（双指针）

由于题目明确指出数组中的元素均为正整数，这赋予了问题一个关键的单调性：对于一个固定的左边界，随着右边界向右扩展，区间和会单调递增。

我们可以利用这一特性，使用滑动窗口（双指针）算法将时间复杂度优化到 $O(N)$ 。

算法步骤：

使用两个指针 left 和 right 来维护一个滑动窗口，并用 currentSum 记录窗口内元素的和。
右指针 right 从左到右遍历数组，每次将 arr[right] 加入 currentSum。
当 currentSum >= x 时，说明我们找到了一个满足条件的区间 [left, right]。
关键优化点：因为所有数字都是正数，所以以 left 为起点，终点在 right 及 right 之后的所有区间（即 [left, right], [left, right+1], ..., [left, N-1]）的和都必然大于等于 x。因此，我们可以直接将 N - right 个区间计入结果，而无需再进行内层循环。
计入结果后，我们需要移动左指针 left 来寻找下一批可能的解。将 arr[left] 从 currentSum 中减去，并将 left 右移一位。
重复此过程，直到 right 遍历完整个数组。

以下是优化后的 Java 代码：

import java.util.Scanner;

/**
 * 标题：数组连续和 | 时间限制：1秒 | 内存限制：65536K | 语言限制：不限
 * 给定一个含有N个正整数的数组, 求出有多少个连续区间（包括单个正整数）, 它们的和大于等于x。
 * 使用滑动窗口算法优化至 O(N) 时间复杂度。
 */
public class ContinuousArraySum {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取第一行 N 和 x
        if (scanner.hasNextLine()) {
            String[] firstLine = scanner.nextLine().split(" ");
            int N = Integer.parseInt(firstLine);
            int x = Integer.parseInt(firstLine);[[source_group_web_8]]

            // 读取第二行数组
            int[] arr = new int[N];
            if (scanner.hasNextLine()) {
                String[] numStrs = scanner.nextLine().split(" ");
                for (int i = 0; i < N; i++) {
                    arr[i] = Integer.parseInt(numStrs[i]);
                }
            }

            int count = 0;
            int left = 0;
            long currentSum = 0; // 使用long防止求和溢出

            // 滑动窗口
            for (int right = 0; right < N; right++) {
                // 1. 扩展右边界
                currentSum += arr[right];

                // 2. 当窗口和满足条件时，统计并收缩左边界
                while (currentSum >= x && left <= right) {
                    // 以left为起点，right为终点的区间满足条件。
                    // 由于都是正整数，[left, right], [left, right+1], ..., [left, N-1]都满足条件。
                    count += N - right;
                    
                    // 收缩左边界，寻找下一个可能的解
                    currentSum -= arr[left];
                    left++;
                }
            }

            System.out.println(count);
        }
        scanner.close();
    }
}

菜单

目录

分享