How to realize region and search in LeetCode
This article shows you how to achieve region and search in LeetCode. The content is concise and easy to understand. It will definitely make your eyes shine. I hope you can gain something through the detailed introduction of this article.
Given an array of integers nums, build a function to find the sum of the elements of the array from index i to j (i ≤ j), containing i, j. For example: input nums = [-2, 0, 3, -5, 2, -1], sumRange(0, 2) =1.
2
answer key
Idea: Dynamic programming, caching This problem can be directly used with the sum function, but it takes a long time. The intermediate state dp[i] represents the sum from 0-i, so the sum of i-j is required to be equal to dp[j]-dp[i-1], so first create an array record dp, and then calculate according to the desired range. Note here that dp[j]-dp[i-1] overflows when i=0, so dp has length len(numbers)+1, and the first element 0 means there is no value before 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(numbers)# param_1 = obj.sumRange(i,j) The above content is how to implement region and retrieval in LeetCode. Have you learned knowledge or skills? If you want to learn more skills or enrich your knowledge reserves, please pay attention to the industry information channel.
