资讯专栏INFORMATION COLUMN

[LintCode] Interval Sum

kelvinlee / 3120人阅读

摘要:很简单的题目,不过要达到的时间,只能用前缀和的方法来做。法前缀和法推荐

Problem

Given an integer array (index from 0 to n-1, where n is the size of this array), and an query list. Each query has two integers [start, end]. For each query, calculate the sum number between index start and end in the given array, return the result list.

Example

For array [1,2,7,8,5], and queries [(0,4),(1,2),(2,4)], return [23,9,20]

Challenge

O(logN) time for each query

Note

很简单的题目,不过要达到O(logn)的时间,只能用前缀和的方法来做。

Solution

1. muggle法

public class Solution {
    public ArrayList intervalSum(int[] A, 
                                       ArrayList queries) {
        ArrayList res = new ArrayList ();
        for (int i = 0; i < queries.size(); i++) {
            int start = queries.get(i).start;
            int end = queries.get(i).end;
            res.add(sum(A, start, end));
        }
        return res;
    }
    public long sum(int[] A, int start, int end) {
        long sum = 0;
        for (int i = start; i <= end; i++) {
            sum += A[i];
        }
        return sum;
    }
}


2. 前缀和法(推荐)

public class Solution {
    public ArrayList intervalSum(int[] A, 
                                       ArrayList queries) {
        ArrayList res = new ArrayList();
        long[] preSum = new long[A.length];
        long sum = 0;
        for (int i = 0; i < A.length; i++) {
            sum += A[i];
            preSum[i] = sum;
        }
        for (Interval i: queries) {
            if (i.start == 0) {
                res.add(preSum[i.end]);
            }
            else {
                res.add(preSum[i.end] - preSum[i.start-1]);
            }
        }
        return res;
    }
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/66196.html

相关文章

  • [LeetCode/LintCode] Merge Intervals

    摘要:方法上没太多难点,先按所有区间的起点排序,然后用和两个指针,如果有交集进行操作,否则向后移动。由于要求的,就对原数组直接进行操作了。时间复杂度是的时间。 Problem Given a collection of intervals, merge all overlapping intervals. Example Given intervals => merged intervals...

    gougoujiang 评论0 收藏0
  • [LintCode] Interval Minimum Number

    摘要:这道题目是筛选出数组中的最小值,存入新数组。因此,联想到和系列的题目,对于的处理,使用线段树是非常有效的方法。之前我们创建的线段树,有和两个。参照这个参数,可以考虑在这道题增加一个的参数,代表每个结点的最小值。 Problem Given an integer array (index from 0 to n-1, where n is the size of this array),...

    taowen 评论0 收藏0
  • [LintCode/LeetCode] Meeting Rooms

    Problem Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings. Example Given intervals = [[0,30],[...

    Noodles 评论0 收藏0
  • [LintCode] Segment Tree Query I & Segment Tree

    摘要:题目是要查询到这个区间内某一点的。值是从最底层的子节点值里取最大值。因此,不用太复杂,递归就可以了。与所不同的是,对所给区间内的元素个数求和,而非筛选。这样就会出现的情况,视作本身处理。 Segment Tree Query Problem For an integer array (index from 0 to n-1, where n is the size of this ar...

    vibiu 评论0 收藏0
  • [LintCode] Teemo Attacking

    Problem In LOL world, there is a hero called Teemo and his attacking can make his enemy Ashe be in poisoned condition. Now, given the Teemos attacking ascending time series towards Ashe and the poison...

    whjin 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<