BOJ. Subsequence sum (1806)

BOJ 1806: Subsequence Sum

All values are positive, so extending the exclusive right boundary can only increase the window sum, and moving the left boundary can only decrease it. For each right boundary, once the sum reaches S, record that window and advance the left boundary while the sum remains at least S. Any longer window ending at the same position cannot improve the answer. The window is [left, right), so its length is exactly right - left; this also handles single-element and first/last windows without special cases. If no window qualifies, the answer remains 0. The scan takes O(N) time because both boundaries move only forward, and uses O(N) space for the input values.

import java.io.BufferedInputStream;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        int n = input.nextInt();
        long target = input.nextLong();
        int[] values = new int[n];
        for (int i = 0; i < n; i++) {
            values[i] = input.nextInt();
        }

        int minLength = n + 1;
        int left = 0;
        long sum = 0;
        int right = 0;
        while (right < n) {
            sum += values[right++];
            while (sum >= target) {
                minLength = Math.min(minLength, right - left);
                sum -= values[left++];
            }
        }

        System.out.println(minLength == n + 1 ? 0 : minLength);
    }

    private static class FastScanner {
        private final BufferedInputStream input = new BufferedInputStream(System.in);
        private final byte[] buffer = new byte[1 << 16];
        private int position;
        private int length;

        private int read() throws IOException {
            if (position == length) {
                length = input.read(buffer);
                position = 0;
                if (length == -1) {
                    return -1;
                }
            }
            return buffer[position++];
        }

        private int nextInt() throws IOException {
            return (int) nextLong();
        }

        private long nextLong() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);

            long value = 0;
            while (c > ' ') {
                value = value * 10 + c - '0';
                c = read();
            }
            return value;
        }
    }
}

const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
const n = input[0];
const target = input[1];
const values = input.slice(2);

let minLength = n + 1;
let left = 0;
let sum = 0;
let right = 0;
while (right < n) {
  sum += values[right++];
  while (sum >= target) {
    minLength = Math.min(minLength, right - left);
    sum -= values[left++];
  }
}

console.log(minLength === n + 1 ? 0 : minLength);