public: NumArray(vector<int>& nums) { m = nums.size() + 1; dp = newint*[m]; for(int i = 0; i < m; ++i) { dp[i] = newint[m]; }
for (int i = 1; i <= nums.size(); ++i) { int sum = 0; for (int j = i; j <= nums.size(); ++j) { sum += nums[j-1]; dp[i][j] = sum; } } } ~NumArray() { for (int i = 0; i < m; ++i) { delete []dp[i]; }
delete []dp; } intsumRange(int i, int j) { return dp[i+1][j+1]; } };
* Your NumArray object will be instantiated and called as such: * NumArray* obj = new NumArray(nums); * int param_1 = obj->sumRange(i,j); */
换成原生数组,时间复杂度仅超过7%,仍然很糟糕。。。
假如直接静态数组int dp[INT_MAX][INT_MAX];,内存会炸掉。。。
官方way
2. 缓存
将计算结果提前存入到 哈希表 中。
PS:而我用的是vector<vector<int>> dp, int **dp, 感觉没区别,应该是resize()/动态分配内存那耗费了不少时间。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
private Map<Pair<Integer, Integer>, Integer> map = new HashMap<>();
public(int[] nums){ for (int i = 0; i < nums.length; i++) { int sum = 0; for (int j = i; j < nums.length; j++) { sum += nums[j]; map.put(Pair.create(i, j), sum); } } }
publicintsumRange(int i, int j){ return map.get(Pair.create(i, j)); }
近期评论