专栏首页专知【Leetcode 303】关关的刷题日记67–Leetcode 303 Range Sum Query – Immutable

【Leetcode 303】关关的刷题日记67–Leetcode 303 Range Sum Query – Immutable

关关的刷题日记67 – Leetcode 303 Range Sum Query – Immutable

题目

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 Note: You may assume that the array does not change. There are many calls to sumRange function.

题目的意思是给定一个数组,求指定子序列的和。数组是不发生变化的,而且会多次求子序列的和。

思路

思路:如果要是每次都遍历数组求子序列和的话,因为会调用很多次肯定会超时。所以我们设置数组re,re[i]表示该数组前i个元素的和。每次调用sumRange的时候,直接返回re[j]-re[i-1]即可。

class NumArray {public:
    vector<int>re;

    NumArray(vector<int> nums) {
        int sum=0;
        for(int i=0; i<nums.size(); i++)
        {
            re.push_back(sum+nums[i]);
            sum=re[i];
        }
    }

    int sumRange(int i, int j) {
        if(i==0)
            return re[j];
        return re[j]-re[i-1];
    }};/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(i,j);
 */

以上就是关关关于这道题的总结经验,希望大家能够理解,有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390,也可以加入专知——Leetcode刷题交流群(请先加微信小助手weixinhao: Rancho_Fang)。

本文分享自微信公众号 - 专知(Quan_Zhuanzhi),作者:关关

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-12-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【专知-关关的刷题日记15】Leetcode 27. Remove Element 方法1、2、3

    题目 Given an array and a value, remove all instances of that value in place and r...

    WZEARW
  • 【Code】关关的刷题日记22——Leetcode 53. Maximum Subarray

    关小刷刷题 22——Leetcode 53. Maximum Subarray 题目 Find the contiguous subarray within a...

    WZEARW
  • 关关的刷题日记94 – Leetcode 153. Find Minimum in Rotated Sorted Array

    点击上方“专知”,关注获取专业AI知识” 关关的刷题日记94 – Leetcode 153. Find Minimum in Rotated Sorted Ar...

    WZEARW
  • 看看附近谁和我一样?

    给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 i 和 j 的差的 绝对值 至...

    公众号袁厨的算法小屋
  • 剑指offer第1题:数组中的重复数字

    之前的刷题都是随心所欲的刷,没有按照什么章程来给各位小伙伴展现。本周开始,小白把LeetCode上面的《剑指offer》,逐一的进行分享吧~会在公众里面开一个专...

    鹏-程-万-里
  • LeetCode 611. 有效三角形的个数(双指针)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/valid-triangle-number 著作权归...

    Michael阿明
  • LeetCode147|丢失的数字

    给定一个包含 [0, n] 中 n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数。

    码农王同学
  • Array - 189. Rotate Array

    189、Rotate Array Given an array, rotate the array to the right by k steps, wher...

    用户5705150
  • 力扣(LeetCode)初级算法--旋转数组

    旋转数组 给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

    程序员小涛
  • 一文带你把这几个经典求和问题按的死死的!

    今天为大家带来三道求和问题,通过文字,图画,动图为大家解析,很容易就能读懂,每道题目都是经典题,大家快来打卡吧。

    公众号袁厨的算法小屋

扫码关注云+社区

领取腾讯云代金券