溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點(diǎn)擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

LeetCode中怎么實(shí)現(xiàn)區(qū)域和檢索

發(fā)布時間：2021-08-12 15:35:14 來源：億速云 閱讀：92 作者：Leah 欄目：大數(shù)據(jù)

本篇文章為大家展示了LeetCode中怎么實(shí)現(xiàn)區(qū)域和檢索，內(nèi)容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細(xì)介紹希望你能有所收獲。

給定一個整數(shù)數(shù)組  nums，建立一個函數(shù)用于求出數(shù)組從索引 i 到 j  (i ≤ j) 范圍內(nèi)元素的總和，包含 i,  j 兩點(diǎn)。如：輸入nums = [-2, 0, 3, -5, 2, -1]，sumRange(0, 2) =1。

2

 題解

思路：動態(tài)規(guī)劃、緩存
本題可以直接用sum函數(shù)，但是耗時較長。中間狀態(tài)dp[i]表示從0-i的和，則要求i-j的和等于dp[j]-dp[i-1]，因此首先建立一個數(shù)組記錄dp，然后根據(jù)想要求的范圍進(jìn)行計算。此處要注意的是，當(dāng)i=0時，dp[j]-dp[i-1]會溢出，所以dp的長度是len(nums)+1，第一個元素為0表示i=0之前沒有值。  
class NumArray:
    def __init__(self, nums: List[int]):        if len(nums)==0:            return        self.dp = [0]*(len(nums)+1)        self.dp[1]=nums[0]        for i in range(2,len(nums)+1):            self.dp[i] = self.dp[i-1]+nums[i-1]
    def sumRange(self, i: int, j: int) -> int:        return self.dp[j+1]-self.dp[i]
# Your NumArray object will be instantiated and called as such:# obj = NumArray(nums)# param_1 = obj.sumRange(i,j)
上述內(nèi)容就是LeetCode中怎么實(shí)現(xiàn)區(qū)域和檢索，你們學(xué)到知識或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識儲備，歡迎關(guān)注億速云行業(yè)資訊頻道。
向AI問一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手