力扣560——和為K的子數組

這道題主要是找規律，優化的時候可以利用哈希表和數組的特性。

原題

給定一個整數數組和一個整數 k，你需要找到該數組中和為 k 的連續的子數組的個數。

示例 1 :

<code>
輸入:nums = [1,1,1], k = 2
輸出: 2 , [1,1] 與 [1,1] 為兩種不同的情況。
/<code>

說明 :

1. 數組的長度為 [1, 20,000]。
2. 數組中元素的範圍是 [-1000, 1000] ，且整數 k 的範圍是 [-1e7, 1e7]。

原題url：
https://leetcode-cn.com/problems/subarray-sum-equals-k/

解題

一開始的想法肯定就是利用暴力解法了，三層 for 循環的那種，第1層和第2層選擇起點和終點，第3層則是計算起點到終點的總和。這樣的想法最簡單，但很可惜，直接超時了，讓我們稍微優化一下。

子數組之和

因為題目要求子數組下標連續，那麼我們想想，如果要求sum(i, j)(也就是從下標 i 到下標 j 的子數組之和)，其實可以轉化成sum(0, i - 1) - sum(0, j)。這樣的話，就可以把上面的三層for循環優化成兩層。

接下來我們直接看看代碼：

<code>
class
 
Solution
 {
    
public
 
int
 
subarraySum
(
int
[] nums, 
int
 k) {
         
        
int
[] sumArray = 
new
 
int
[nums.length];
        sumArray[
0
] = nums[
0
];
        
for
 (
int
 i = 
1
; i < nums.length; i++) {
            sumArray[i] = sumArray[i - 
1
] + nums[i];
        }

        
int
 result = 
0
;
        
int
 sum = 
0
;
         
for
 (
int
 i = sumArray.length - 
1
; i >= 
0
; i--) {
             
            
if
 (sumArray[i] == k) {
                result++;
            }
             
            
for
 (
int
 j = i - 
1
; j >= 
0
 && j != i; j--) {
                sum = sumArray[i] - sumArray[j];
                
if
 (sum == k) {
                    result++;
                }
            }
        }
        
return
 result;
    }
}/<code>

提交OK，但時間複雜度是O(n^2)，優化一下。

用哈希表優化

我們想想，上面使用使用第二層for循環，主要是為了查出 sumArray 中是否還存在等於sumArray[i] - k的數，這明顯是一個映射關係，因此我們用一個 map 去記錄中間的求和結果。

<code>
class
 
Solution
 {
    
public
 
int
 
subarraySum
 
(
int
[] nums, 
int
 k) {
         
         
        Map> 
map
 = 
new
 HashMap<>(nums.length * 
4
 / 
3
 + 
1
);
         
        
int
 sum = 
0
;
         
        Set sumSet = 
new
 HashSet<>();
        
for
 (
int
 i = 
0
; i < nums.length; i++) {
            sum += nums[i];
            sumSet.add(sum);
             
            List indexList = 
map
.get(sum);
            
if
 (indexList == null) {
                indexList = 
new
 LinkedList<>();
            }
            indexList.add(i);
            
map
.put(sum, indexList);
        }

        
int
 result = 
0
;
        
for
 (Integer subSum : sumSet) {
            List 
list
 = 
map
.get(subSum);
             
             
if
 (
list
 == null) {
                
continue
;
            }
            
if
 (subSum == k) {
                result += 
map
.get(subSum).size();
            }
             
            
int
 remainSum = subSum - k;
            List remainList = 
map
.get(remainSum);
             
            
if
 (remainList == null) {
                
continue
;
            }

             
             
            
for
 (
int
 index1 : 
list
) {
                
for
 (
int
 index2 : remainList) {
                    
if
 (index1 <= index2) {
                        
continue
;
                    }

                    result++;
                }
            }
        }
        
return
 result;
    }
}/<code>

提交OK，雖然較之前的方法時間效率上有所提高，但並沒有本質區別。特別是最後的雙重 for 循環，因為下標只有大的減小的才有意義，這樣也就給自己額外增加了運算。

那麼反思一下，是否真的有必要提前算好子數組的和？如果一邊遍歷一邊求和，並將求和的結果存入map中，那麼 map 中存在的，一定是下標小於自己的求和結果。針對這點，我們可以再做一步優化：

<code>
public
 
class
 
Solution
 {
    
public
 
int
 
subarraySum
(
int
[] nums, 
int
 k) {
         
        
int
 count = 
0
;
         
        
int
 sum = 
0
;
         
        HashMap 
map
 = 
new
 HashMap<>();
         
        
map
.put(
0
, 
1
);
         
        
for
 (
int
 i = 
0
; i < nums.length; i++) {
             
            sum += nums[i];
             
            
if
 ( 
map
.containsKey(sum - k)) {
                 
                count += 
map
.get(sum - k);
            }
             
            
map
.put(sum, 
map
.getOrDefault(sum, 
0
) + 
1
);
        }
        
return
 count;
    }
}/<code>

提交OK，這樣時間複雜度就變為了O(n)。

數據結構的優化

現在，我們用哈希表來存儲中間結果。雖然哈希表的查找效率理論上可以達到O(1)，但考慮到哈希衝突，最壞情況下還是有可能達到O(n)。真正能夠保證達到O(1)的數據結構，是數組（用空間換取時間）。

那這個用來存儲的一維數組究竟長度該設置為多少呢？自然就是找出數組中子數組之和的最大值和最小值，兩者求差，結果就是最終的數組長度。利用這個數組去存儲子數組求和的結果，這樣就能保證在查找時的效率了。

<code>
class
 
Solution
 {
    
public 
 int subarraySum(int[] nums, int k) {
        int sum = 
0
;
         
        int 
min
 = 
0
;
        int 
max
 = 
0
;
         
        
for
 (int n : nums) {
            sum += n;
            
min
 = 
Math
.
min
(
min
, sum);
            
max
 = 
Math
.
max
(
max
, sum);
        }
         
         
        int[] sums = new int[
max
 - 
min
 + 
1
];
         
        int 
count
 = 
0
;
        sum = 
0
;
         
         
        
for
 (int n : nums) {
             
            sum += n;
             
            int target = sum - 
min
 - k;
             
            
if
 (target >= 
0
 && target < sums.length) {
                 
count
 += sums[target];
            }

            sums[sum - 
min
]++;
        }
         
        
if
 (k - 
min
 >= 
0
 && k - 
min
 < sums.length) {
            
count
 += sums[k - 
min
];
        }
        
return
 
count
;
    }
}/<code>

提交OK，執行時間上更快了。

總結

以上就是這道題目我的解答過程了，不知道大家是否理解了。這道題主要是找規律，優化的時候可以利用哈希表和數組的特性。

有興趣的話可以訪問我的博客或者關注我的公眾號、頭條號，說不定會有意外的驚喜。

https://death00.github.io/

關鍵字: min sumArray 示例