Skip to content

前缀和优化版,设置前缀和数组长度为原数组长度+1 #2902

Open
@Hydrion-Qlz

Description

@Hydrion-Qlz

关于前缀和的讲解的时候,可以将sum数组的size建为n+1,这样在计算区间和的时候可以直接通过 preSum[b + 1] - preSum[a]计算,省去了关于a==0的判断

原文链接:https://programmercarl.com/kamacoder/0058.%E5%8C%BA%E9%97%B4%E5%92%8C.html#%E6%80%9D%E8%B7%AF

优化后的代码

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int[] preSum = new int[n + 1];
        int sum = 0;
        for (int i = 1; i < preSum.length; i++) {
            sum += arr[i - 1];
            preSum[i] = sum;
        }

        while (sc.hasNext()) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            
            System.out.println(preSum[b + 1] - preSum[a]);
        }

        sc.close();
    }
}

原代码

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] vec = new int[n];
        int[] p = new int[n];

        int presum = 0;
        for (int i = 0; i < n; i++) {
            vec[i] = scanner.nextInt();
            presum += vec[i];
            p[i] = presum;
        }

        while (scanner.hasNextInt()) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();

            int sum;
            if (a == 0) {
                sum = p[b];
            } else {
                sum = p[b] - p[a - 1];
            }
            System.out.println(sum);
        }

        scanner.close();
    }
}

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions