截止到目前我已經寫了 600多道演算法題，其中部分已經整理成了pdf檔案，目前總共有1000多頁（并且還會不斷的增加），大家可以免費下載
下載鏈接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取碼：6666
來看下代碼
public int subarraySum(int[] nums, int k) {
int count = 0;
for (int j = 0; j < nums.length; j++) {
for (int i = 0; i <= j; i++) {
int sum = 0;
//計算子陣列[i……j]中所有數字的和
for (int m = i; m <= j; m++) {
sum += nums[m];
}
//如果子陣列[i……j]中所有數字
//的和等于k，count加1
if (sum == k)
count++;
}
}
return count;
}
時間復雜度：O(n^3)，
空間復雜度：O(1)，
這種時間復雜度太高，當資料量比較大的時候，很容易超時，我們再來優化一下，當我們以nums[j]為子陣列最后一個元素的時候，不用每次都列舉子陣列[i……j]之間所有元素的和，只需要以nums[j]為最后一個元素，從后往前累加，即可計算以nums[j]為最后一個元素的連續子陣列，比較繞，來看個圖
來看下代碼
public int subarraySum(int[] nums, int k) {
int count = 0;
for (int j = 0; j < nums.length; j++) {
//sum是以nums[j]為最后一個元素，
//從后往前累加的值
int sum = 0;
for (int i = j; i >= 0; i--) {
sum += nums[i];
//如果子陣列的和等于k，count就加1
if (sum == k) {
count++;
}
}
}
return count;
}
時間復雜度：O(n^2)，
空間復雜度：O(1)，
時間復雜度從n^3降到了n^2，我們再來看一個時間復雜度為n的解決方式，就是前綴和，
public int subarraySum(int[] nums, int k) {
//先計算前綴和，pre[i]表示陣列nums中前i個元素的和
int[] pre = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
pre[i + 1] = pre[i] + nums[i];
}
int count = 0;
Map<Integer, Integer> map = new HashMap<>();
for (int j = 0; j <= nums.length; j++) {
//計算pre[i-1]+pre[j]=k，我們只需要找出pre[i-1]
//的個數即可，這個可以通過map來查找
int other = pre[j] - k;
if (map.containsKey(other)) {
//如果map中存在pre[i-1]，把他的個數進行累加
count += map.get(other);
}
//pre[j]的個數加1在放到map中
map.put(pre[j], map.getOrDefault(pre[j], 0) + 1);
}
return count;
}
時間復雜度：O(n)，
空間復雜度：O(n)，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/301754.html
標籤：java
上一篇：初識Java語言（七）- String、StringBuilder和 StringBuffer三者之間的區別和聯系！！！【建議收藏】