程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> leetcode筆記:Range Sum Query

leetcode筆記:Range Sum Query

編輯:關於C++

一. 題目描述

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

二. 題目分析

給定一個數組nums,求出下標ij之間元素的和,這裡假設i一定是小於或等於j的,且數組nums一般是不變的。

這道題應該不看提示就能想到比暴力方法更好的方案,在本題中,sumRange可能會被調用多次,因此如果每次調用時才對下標區間的元素進行累加,會導致效率低下。

可以采取的改進方法是,在構造函數NumArray(vector &nums)中,輸入了數組nums,同時計算了從第一個元素到每個下標元素所有元素的累積和,保存到新數組sums的對應位置中,這樣,每次尋找下標ij之間元素的和,只需直接返回: sums[j] - sum[i - 1]即可。

三. 示例代碼

class NumArray {
public:
    NumArray(vector &nums) {
        if (nums.empty()) return;
        else
        {
            sums.push_back(nums[0]);
            //求得給定數列長度
            int len = nums.size();
            for (int i = 1; i < len; ++i)
                sums.push_back(sums[i - 1] + nums[i]);
        }
    }

    int sumRange(int i, int j) {
        return sums[j] - sums[i - 1];
    }

private:
    //存儲數列和
    vector sums;
};

// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.sumRange(1, 2);
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved