這是悅樂書的第204次更新,第214篇原創
01 看題和準備
今天介紹的是LeetCode算法題中Easy級别的第70題(順位題号是303)。給定整數數組nums,找到索引i和j(i≤j)之間的元素之和,包括端點。例如:
給定nums = [-2,0,3,-5,2,-1]
sumRange(0,2) - > 1
sumRange(2,5) - > -1
sumRange(0,5) - > -3
注意:
- 您可以假設數組不會更改。
- sumRange函數有很多調用。
本次解題使用的開發工具是eclipse,jdk使用的版本是1.8,環境是win7 64位系統,使用Java語言編寫和測試。
02 第一種解法
使用暴力解法,直接使用for循環依次将i到j之間的元素求和,最後再傳回其和。
此解法空間複雜度是O(1),時間複雜度是O(n)。
class NumArray {
public int[] arr;
public NumArray(int[] nums) {
arr = nums;
}
public int sumRange(int i, int j) {
int sum = 0;
for (int k=i; k<= j; k++) {
sum += arr[k];
}
return sum;
}
}
03 第二種解法
如果使用第一種解法,sumRange的方法調用次數太多,并且每次都要重新開始計算,我們可以事先把不同位置元素的和算出來存到另外一個數組中,在sumRange中直接去新數組中取對應位置的和做減法即可。
此解法時間複雜度是O(1),空間複雜度是O(n)。
class NumArray2 {
public int[] sum;
public NumArray2(int[] nums) {
sum = new int[nums.length+1];
for (int i=0; i<nums.length; i++) {
sum[i+1] = nums[i] + sum[i];
}
}
public int sumRange(int i, int j) {
return sum[j+1] - sum[i];
}
}
04 小結
算法專題目前已連續日更超過兩個月,算法題文章70+篇,公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞,擷取系列文章合集。
以上就是全部内容,如果大家有什麼好的解法思路、建議或者其他問題,可以下方留言交流,點贊、留言、轉發就是對我最大的回報和支援!