leetcode 303. Range Sum Query - Immutable 字串求和 + DP

￡神魔★判官ぃ 2022-06-06 23:06 138阅读 0赞

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:  
Given nums = \[-2, 0, 3, -5, 2, -1\]

sumRange(0, 2) -> 1  
sumRange(2, 5) -> -1  
sumRange(0, 5) -> -3

题意很简单，就是一个基本的求和问题，要是直接求的化，肯定超时，所以可以使用DP的思想。

代码如下：

import java.util.ArrayList;
    import java.util.List;
    
    
    /*
     * 这里的求和部分使用的的是DP部分，不能直接求和，会超时的
     * */
    public class NumArray 
    {
        
        List<Integer> list=new ArrayList<Integer>();
        public NumArray(int[] nums) 
        {
            if(nums==null || nums.length<=0)
                return ;
            list.add(nums[0]);
            for(int i=1;i<nums.length;i++)
                list.add(nums[i]+list.get(i-1));
        }
    
        public int sumRange(int i, int j) 
        {
            if(list.size()<=0|| i<0 || i>=list.size() || j<0 || j>list.size())
                return 0;     
            if(i==0)
                return list.get(j);
            else 
                return list.get(j)-list.get(i-1);
        }
    }
    
    /**
     * Your NumArray object will be instantiated and called as such:
     * NumArray obj = new NumArray(nums);
     * int param_1 = obj.sumRange(i,j);
     */

发表评论取消回复

表情：

评论列表（有 0 条评论，138人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 303. Range Sum Query - Immutable | 303. 区域和检索 - 数组不可变（一维前缀和问题）

题目 [https://leetcode.com/problems/range-sum-query-immutable/][https_leetcode.com_prob

分手后的思念是犯贱/ 2022年10月13日 05:28/ 0 赞/ 166 阅读

相关 leetcode（303）Range Sum Query - Immutable js代码实现

Sum Query - Immutable Given an integer array nums, find the sum of the elements betwe

叁歲伎倆/ 2022年08月18日 12:11/ 0 赞/ 107 阅读

相关 LeetCode303——Range Sum Query - Immutable

LeetCode303——Range Sum Query - Immutable 插播一条新题题意：找出数组指定两个索引之间所有元素之和。按照Lee

小咪咪/ 2022年08月10日 09:22/ 0 赞/ 109 阅读

相关 leetcode 307. Range Sum Query - Mutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j

比眉伴天荒/ 2022年07月26日 12:15/ 0 赞/ 122 阅读

相关 [leetcode]: 303. Range Sum Query - Immutable

1.题目 Given an integer array nums, find the sum of the elements between indices i and

谁践踏了优雅/ 2022年06月14日 10:54/ 0 赞/ 108 阅读

相关 leetcode 303. Range Sum Query - Immutable 字串求和 + DP

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j

￡神魔★判官ぃ/ 2022年06月06日 23:06/ 0 赞/ 139 阅读

相关 leetcode 304. Range Sum Query 2D - Immutable 子矩阵求和 + DP

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by i

秒速五厘米/ 2022年06月06日 23:06/ 0 赞/ 136 阅读

相关 Range Sum Query - Immutable

303. Range Sum Query - Immutable 题目描述 Given an integer array nums, find the sum of

缺乏、安全感/ 2022年05月14日 12:35/ 0 赞/ 131 阅读

相关 304. Range Sum Query 2D - Immutable

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by i

Bertha 。/ 2022年03月06日 06:42/ 0 赞/ 128 阅读

相关 LeetCode:303. Range Sum Query - Immutable 数组范围内求和

试题： Given an integer array nums, find the sum of the elements between indices i and j

╰+哭是因爲堅強的太久メ/ 2021年06月24日 16:10/ 0 赞/ 325 阅读