程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode 303 Range Sum Query - Immutable(范圍總和查詢-永久不變)(*)

LeetCode 303 Range Sum Query - Immutable(范圍總和查詢-永久不變)(*)

編輯:C++入門知識

LeetCode 303 Range Sum Query - Immutable(范圍總和查詢-永久不變)(*)


翻譯

給定一個整型數組nums,找出在索引i到j(i小於等於j)之間(包括i和j)的所有元素之和。

例如:
給定nums = [-2,0,3,-5,2,-1]

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

批注:
你可以假定這個數組不會改變。
這裡會有很多次對sumRange函數的調用。

原文

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.

分析

一開始我還以為這個題有多簡單呢,就寫了下面這個代碼:

class NumArray {
public:
    vector numArray;
    NumArray(vector &nums) {
        numArray = nums;
    }
    int sumRange(int i, int j) {
        int sum = 0;
        while (i < j) {
            sum += numArray[i++];
        }
        return sum;
    }
};

因為不知道需要構造函數干嘛,所以硬生生的加了這麼一句進去,其實完全沒用。功能是實現了,但是面對題目變態的測試用例,果然還是崩了。

至於題目測試用例有多變態,數據來說話:一共214513個字符,其中包括了nums的數據,也包括了函數調用,nums的長度沒去算,但是sumRange函數的調用次數高達10000次。

看到這個測試用例,就明白要針對函數調用做優化,一個不錯的辦法是將所有的返回的值:

從0到1的所有元素之和,
從0到2的所有元素之和,
從0到10000的所有元素之和,
………………

然後計算i和j之間所有元素之和的時候,(因為包含了i和j),也就是求從0到j的所有元素之和減去從0到i-1的所有元素之和。

所以代碼就如下所示了,但是時間上還是使用了624ms叻。

class NumArray {
public:
    map rangeSum;
    NumArray(vector &nums) {
        int sum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            sum += nums[i];
            rangeSum.insert(pair(i, sum));
        }
    }

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

雖然對底層的具體實現不是很了解,但因為有索引,所以我自覺用vector的話查找其值來跟快速;而且添加值也更加快速,因為只是一個值而不用是鍵值對。

具體代碼如下:

代碼

class NumArray {
public:
    vector rangeSum;

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

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved