得了，一文把字首和給扒的乾乾淨淨了。

今天我們來說一下刷題時經常用到的字首和思想，字首和思想和滑動視窗會經常用在求子陣列和子串問題上，當我們遇到此類問題時，則應該需要想到此類解題方式，該文章深入淺出描述字首和思想，讀完這個文章就會有屬於自己的解題框架，遇到此類問題時就能夠輕鬆應對。

下面我們先來了解一下什麼是字首和。

字首和其實我們很早之前就瞭解過的，我們求數列的和時，Sn = a1+a2+a3+...an; 此時Sn就是數列的前 n 項和。例 S5 = a1 + a2 + a3 + a4 + a5; S2 = a1 + a2。所以我們完全可以通過 S5-S2 得到 a3+a4+a5 的值，這個過程就和我們做題用到的字首和思想類似。我們的字首和陣列裡儲存的就是前 n 項的和。見下圖

我們通過字首和陣列儲存前 n 位的和，presum[1]儲存的就是 nums 陣列中前 1 位的和，也就是 presum[1] = nums[0], presum[2] = nums[0] + nums[1] = presum[1] + nums[1]. 依次類推，所以我們通過字首和陣列可以輕鬆得到每個區間的和。

例如我們需要獲取 nums[2] 到 nums[4] 這個區間的和，我們則完全根據 presum 陣列得到，是不是有點和我們之前說的字串匹配演演算法中 BM,KMP 中的 next 陣列和 suffix 陣列作用類似。那麼我們怎麼根據 presum 陣列獲取 nums[2] 到 nums[4] 區間的和呢？見下圖

好啦，我們已經瞭解了字首和的解題思想了，我們可以通過下面這段程式碼得到我們的字首和陣列，非常簡單

 for (int i = 0; i < nums.length; i++) {
      presum[i+1] = nums[i] + presum[i];
 }

好啦，我們開始實戰吧。

leetcode 724. 尋找陣列的中心索引

題目描述

給定一個整數型別的陣列 nums，請編寫一個能夠返回陣列 「中心索引」 的方法。

我們是這樣定義陣列 中心索引 的：陣列中心索引的左側所有元素相加的和等於右側所有元素相加的和。

如果陣列不存在中心索引，那麼我們應該返回 -1。如果陣列有多箇中心索引，那麼我們應該返回最靠近左邊的那一個。

範例 1：

輸入：
nums = [1, 7, 3, 6, 5, 6]
輸出：3

解釋：
索引 3 (nums[3] = 6) 的左側數之和 (1 + 7 + 3 = 11)，與右側數之和 (5 + 6 = 11) 相等。
同時, 3 也是第一個符合要求的中心索引。

範例 2：

輸入：
nums = [1, 2, 3]
輸出：-1

解釋：
陣列中不存在滿足此條件的中心索引。

理解了我們字首和的概念（不知道好像也可以做，這個題太簡單了哈哈）。我們可以一下就能把這個題目做出來，先遍歷一遍求出陣列的和，然後第二次遍歷時，直接進行對比左半部分和右半部分是否相同，如果相同則返回 true，不同則繼續遍歷。

class Solution {
    public int pivotIndex(int[] nums) {
        int presum = 0;
        //陣列的和
        for (int x : nums) {
           presum += x;
        }      
        int leftsum = 0;
        for (int i = 0; i < nums.length; ++i) {
            //發現相同情況
            if (leftsum == presum - nums[i] - leftsum) {
                return i;
            }
            leftsum += nums[i];          
        }
        return -1;
    }
}

leetcode 560. 和為K的子陣列

題目描述

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

範例 1 :

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

暴力法

解析

我們先來用暴力法解決這個題目，很簡單，一下就能 AC。

這個題目的題意很容易理解，就是讓我們返回和為 k 的子陣列的個數，所以我們直接利用雙重回圈解決該題，這個是很容易想到的。我們直接看程式碼吧。

class Solution {
    public int subarraySum(int[] nums, int k) {
         int len = nums.length;
         int sum = 0;
         int count = 0;
         //雙重回圈
         for (int i = 0; i < len; ++i) {
             for (int j = i; j < len; ++j) {
                 sum += nums[j];
                 //發現符合條件的區間
                 if (sum == k) {
                     count++;
                 }
             }
             //記得歸零，重新遍歷
             sum = 0;
         }
         return count;
    }
}

好啦，既然我們已經知道如何求字首和陣列了，那我們來看一下如何用字首和思想來解決這個問題。

class Solution {
    public int subarraySum(int[] nums, int k) {
        //字首和陣列
        int[] presum = new int[nums.length+1];
        for (int i = 0; i < nums.length; i++) {
            //這裡需要注意，我們的字首和是presum[1]開始填充的
            presum[i+1] = nums[i] + presum[i];
        }
        //統計個數
        int count = 0;
        for (int i = 0; i < nums.length; ++i) {
            for (int j = i; j < nums.length; ++j) {
                //注意偏移，因為我們的nums[2]到nums[4]等於presum[5]-presum[2]
                //所以這樣就可以得到nums[i,j]區間內的和
                if (presum[j+1] - presum[i] == k) {
                    count++;
                }
            }
        }
        return count;
    }
}

我們分析上面的程式碼，發現該程式碼雖然用到了字首和陣列，但是對比暴力法並沒有提升效能，時間複雜度仍為O(n^2)，空間複雜度成了 O(n)。那我們有沒有其他方法解決呢？

字首和 + HashMap

瞭解這個方法前，我們先來看一下下面這段程式碼，保證你很熟悉

class Solution {
    public int[] twoSum(int[] nums, int target) {

        HashMap<Integer,Integer> map  = new HashMap<>();
        //一次遍歷
        for (int i = 0; i < nums.length; ++i) {
            //存在時，我們用陣列得值為 key，索引為 value
            if (map.containsKey(target - nums[i])){              
               return new int[]{i,map.get(target-nums[i])};
            }
            //存入值
            map.put(nums[i],i);
        }
        //返回
        return new int[]{};
    }
}

上面的這段程式碼是不是賊熟悉，沒錯就是那個快被我們做爛的兩數之和。這一段程式碼就是用到了我們的字首和+ HashMap 思想，那麼我們如何通過這個方法來解決這個題目呢？

在上面的程式碼中，我們將陣列的值和索引存入 map 中，當我們遍歷到某一值 x 時，判斷 map 中是否含有 target - x，即可。

其實我們現在這個題目和兩數之和原理是一致的，只不過我們是將所有的字首和該字首和出現的次數存到了 map 裡。下面我們來看一下程式碼的執行過程。


我們來拆解一下動圖，可能有的同學會思考為什麼我們只要檢視是否含有 presum - k ，並獲取到presum - k 出現的次數就行呢？見下圖，所以我們完全可以通過 presum - k的個數獲得 k 的個數

好啦我們來看一下程式碼吧

class Solution {
    public int subarraySum(int[] nums, int k) {
        if (nums.length == 0) {
            return 0;
        }
        HashMap<Integer,Integer> map = new HashMap<>();
        //細節，這裡需要預存字首和為 0 的情況，會漏掉前幾位就滿足的情況
        //例如輸入[1,1,0]，k = 2 如果沒有這行程式碼，則會返回0,漏掉了1+1=2，和1+1+0=2的情況
        //輸入：[3,1,1,0] k = 2時則不會漏掉
        //因為presum[3] - presum[0]表示前面 3 位的和，所以需要map.put(0,1),墊下底
        map.put(0, 1);
        int count = 0;
        int presum = 0;
        for (int x : nums) {
            presum += x;
            //當前字首和已知，判斷是否含有 presum - k的字首和，那麼我們就知道某一區間的和為 k 了。
            if (map.containsKey(presum - k)) {
                count += map.get(presum - k);//獲取次數
            }
            //更新
            map.put(presum,map.getOrDefault(presum,0) + 1);
        }
        return count;
    }
}

做完這個題目，各位也可以去完成一下這個題目，兩個題目幾乎完全相同 leetcode 930. 和相同的二元子陣列

leetcode1248. 統計「優美子陣列」

題目描述

給你一個整數陣列 nums 和一個整數 k。

如果某個 連續 子陣列中恰好有 k 個奇數數位，我們就認為這個子陣列是「優美子陣列」。

請返回這個陣列中「優美子陣列」的數目。

範例 1：

輸入：nums = [1,1,2,1,1], k = 3
輸出：2
解釋：包含 3 個奇數的子陣列是 [1,1,2,1] 和 [1,2,1,1] 。

範例 2：

輸入：nums = [2,4,6], k = 1
輸出：0
解釋：數列中不包含任何奇數，所以不存在優美子陣列。

範例 3：

輸入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
輸出：16

如果上面那個題目我們完成了，這個題目做起來，分分鐘的事，不信你去寫一哈，百分百就整出來了，我們繼續按上面的思想來解決。

HashMap

解析

上個題目我們是求和為 K 的子陣列，這個題目是讓我們求 恰好有 k 個奇數數位的連續子陣列，這兩個題幾乎是一樣的，上個題中我們將字首區間的和儲存到雜湊表中，這個題目我們只需將字首區間的奇數個數儲存到區間內即可，只不過將 sum += x 改成了判斷奇偶的語句，見下圖。

我們來解析一下雜湊表，key 代表的是含有 1 個奇數的字首區間，value 代表這種子區間的個數，含有兩個，也就是nums[0],nums[0,1].後面含義相同，那我們下面直接看程式碼吧，一下就能讀懂。

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        
        if (nums.length == 0) {
            return 0;
        }
        HashMap<Integer,Integer> map = new HashMap<>();
        //統計奇數個數，相當於我們的 presum
        int oddnum = 0;
        int count = 0;
        map.put(0,1);
        for (int x : nums) {
            // 統計奇數個數
            oddnum += x & 1;
            // 發現存在，則 count增加
            if (map.containsKey(oddnum - k)) {
             count += map.get(oddnum - k);
            }
            //存入
            map.put(oddnum,map.getOrDefault(oddnum,0)+1);
        }
        return count;
    }
}

但是也有一點不同，就是我們是統計奇數的個數，陣列中的奇數個數肯定不會超過原陣列的長度，所以這個題目中我們可以用陣列來模擬 HashMap ，用陣列的索引來模擬 HashMap 的 key，用值來模擬雜湊表的 value。下面我們直接看程式碼吧。

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {      
        int len = nums.length;
        int[] map = new int[len + 1];
        map[0] = 1;
        int oddnum = 0;
        int count = 0;
        for (int i = 0; i < len; ++i) {
            //如果是奇數則加一，偶數加0，相當於沒加
            oddnum += nums[i] & 1;
            if (oddnum - k >= 0) {
                count += map[oddnum-k];
            }
            map[oddnum]++;
        }
        return count;
    }
}

leetcode 974 和可被 K 整除的子陣列

題目描述

給定一個整數陣列 A，返回其中元素之和可被 K 整除的（連續、非空）子陣列的數目。

範例：

輸入：A = [4,5,0,-2,-3,1], K = 5
輸出：7

解釋：

有 7 個子陣列滿足其元素之和可被 K = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

字首和+HashMap

解析

我們在該文的第一題 **和為K的子陣列 **中，我們需要求出滿足條件的區間，見下圖

我們需要找到滿足，和為 K 的區間。我們此時 presum 是已知的，k 也是已知的，我們只需要找到 presum - k區間的個數，就能得到 k 的區間個數。但是我們在當前題目中應該怎麼做呢？見下圖。

我們在之前的例子中說到，presum[j+1] - presum[i] 可以得到 nums[i] + nums[i+1]+.... nums[j]，也就是[i,j]區間的和。

那麼我們想要判斷區間 [i,j] 的和是否能整除 K，也就是上圖中紫色那一段是否能整除 K，那麼我們只需判斷

(presum[j+1] - presum[i] ) % k 是否等於 0 即可，

我們假設 (presum[j+1] - presum[i] ) % k == 0；則

presum[j+1] % k - presum[i] % k == 0;

presum[j +1] % k = presum[i] % k ;

我們 presum[j +1] % k 的值 key 是已知的，則是當前的 presum 和 k 的關係，我們只需要知道之前的字首區間裡含有相同餘數 （key）的個數。則能夠知道當前能夠整除 K 的區間個數。見下圖

題目程式碼

class Solution {
    public int subarraysDivByK(int[] A, int K) {
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0,1);
        int presum = 0;
        int count = 0;
        for (int x : A) {
             presum += x;
             //當前 presum 與 K的關係，餘數是幾，當被除數為負數時取模結果為負數，需要糾正
             int key = (presum % K + K) % K;
             //查詢雜湊表獲取之前key也就是餘數的次數
             if (map.containsKey(key)) {
                 count += map.get(key);
             }
             //存入雜湊表當前key，也就是餘數
             map.put(key,map.getOrDefault(key,0)+1);
        }
        return count;
    }
}

我們看到上面程式碼中有一段程式碼是這樣的

int key = (presum % K + K) % K;

這是為什麼呢？不能直接用 presum % k 嗎？

這是因為當我們 presum 為負數時，需要對其糾正。糾正前(-1) %2 = (-1)，糾正之後 ( (-1) % 2 + 2) % 2=1 儲存在雜湊表中的則為 1.則不會漏掉部分情況，例如輸入為 [-1,2,9],K = 2如果不對其糾正則會漏掉區間 [2] 此時 2 % 2 = 0，符合條件，但是不會被計數。

那麼這個題目我們可不可以用陣列，代替 map 呢？當然也是可以的，因為此時我們的雜湊表存的是餘數，餘數最大也只不過是 K-1所以我們可以用固定長度 K 的陣列來模擬雜湊表。

class Solution {
    public int subarraysDivByK(int[] A, int K) {
        int[] map = new int[K];
        map[0] = 1;
        int len = A.length;
        int presum = 0;
        int count = 0;
        for (int i = 0; i < len; ++i) {
            presum += A[i];
            //求key
            int key = (presum % K + K) % K;
            //count新增次數，並將當前的map[key]++;
            count += map[key]++;         
        }
        return count;
    }
}

leetcode 523 連續的子陣列和

題目描述

給定一個包含 非負數 的陣列和一個目標 整數 k，編寫一個函數來判斷該陣列是否含有連續的子陣列，其大小至少為 2，且總和為 k 的倍數，即總和為 n*k，其中 n 也是一個整數。

範例 1：

輸入：[23,2,4,6,7], k = 6
輸出：True

解釋：[2,4] 是一個大小為 2 的子陣列，並且和為 6。

範例 2：

輸入：[23,2,6,4,7], k = 6
輸出：True

解釋：[23,2,6,4,7]是大小為 5 的子陣列，並且和為 42。

字首和 + HashMap

這個題目算是對剛才那個題目的升級，前半部分是一樣的，都是為了讓你找到能被 K 整除的子陣列，但是這裡加了一個限制，那就是子陣列的大小至少為 2，那麼我們應該怎麼判斷子陣列的長度呢？我們可以根據索引來進行判斷，見下圖。

此時我們 K = 6, presum % 6 = 4 也找到了相同餘數的字首子陣列 [0,1] 但是我們此時指標指向為 2，我們的字首子區間 [0,1]的下界為1，所以 2 - 1 = 1，但我們的中間區間的長度小於2，所以不能返回 true，需要繼續遍歷，那我們有兩個區間[0,1],[0,2]都滿足 presum % 6 = 4，那我們雜湊表中儲存的下標應該是 1 還是 2 呢？我們儲存的是1，如果我們儲存的是較大的那個索引，則會出現下列情況，見下圖。

此時，仍會顯示不滿足子區間長度至少為 2 的情況，仍會繼續遍歷，但是我們此時的 [2,3]區間已經滿足該情況，返回 true，所以我們往雜湊表存值時，只存一次，即最小的索引即可。下面我們看一下該題的兩個細節

細節1：我們的 k 如果為 0 時怎麼辦，因為 0 不可以做除數。所以當我們 k 為 0 時可以直接存到陣列裡，例如輸入為 [0,0] , K = 0 的情況

細節2：另外一個就是之前我們都是統計個數，value 裡儲存的是次數，但是此時我們加了一個條件就是長度至少為 2，儲存的是索引，所以我們不能繼續 map.put(0,1)，應該賦初值為 map.put(0,-1)。這樣才不會漏掉一些情況，例如我們的陣列為[2,3,4],k = 1,當我們 map.put(0,-1) 時，當我們遍歷到 nums[1] 即 3 時，則可以返回 true，因為 1-（-1）= 2，5 % 1=0 , 同時滿足。

視訊解析


題目程式碼

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        HashMap<Integer,Integer> map = new HashMap<>();
        //細節2
        map.put(0,-1);
        int presum = 0;
        for (int i = 0; i < nums.length; ++i) {
            presum += nums[i];
            //細節1，防止 k 為 0 的情況
            int key = k == 0 ? presum : presum % k;
            if (map.containsKey(key)) {
                if (i - map.get(key) >= 2) {
                     return true;
                }
                //因為我們需要儲存最小索引，當已經存在時則不用再次存入，不然會更新索引值
                continue;           
            } 
            map.put(key,i);                  
        }
        return false;
    }
}

好啦，字首和能寫的都在這了，看完妥妥的搞定這些題目，很簡單，而且還會有自己的解題思維，遇到類似題目一點不慌。

另外我們新建了一個刷題打卡小隊，每天用小程式打卡，互相監督，群內還有幾位大佬進行指導講解，個人認為還不錯。需要的可以看我簡介，
另外還聯合幾位老哥整理了一份經典必刷題，題目大綱，需要的可以看我的個人簡介，在小屋內點選刷題大綱檢視。