一、題目描述

給定一個整數(shù)數(shù)組 nums 和一個整數(shù) k ，返回其中元素之和可被 k 整除的（連續(xù)、非空） 子數(shù)組 的數(shù)目。

子數(shù)組 是數(shù)組的 連續(xù) 部分。

示例：

輸入：nums = [4,5,0,-2,-3,1]，k = 5

輸出：7

輸入：nums = [ 5 ]，k = 9

輸出：0

二、題解

思路分析

首先我們很容易想到暴力枚舉的方法，即遍歷數(shù)組，在遍歷每個元素的同時向后尋找元素之和能夠被k整除的子數(shù)組

暴力枚舉代碼如下：

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
       int ret = 0;
       for(int i = 0; i < nums.length; i++){
           int sum = 0;
           for(int j = i; j < nums.length; j++){
               sum += nums[j];
               if(sum % k == 0){
                   ret++;
               }
           }
       }
       return ret;
    }
}

其時間復(fù)雜度為O()，當(dāng)輸入的nums數(shù)組較大時，會超出時間限制，因此，暴力枚舉方式行不通，我們繼續(xù)考慮其他方法

題目中要求我們找到元素之和可被k整除的（連續(xù)、非空）子數(shù)組，因此我們可以想到使用雙指針的思路，即考慮使用滑動窗口來解決這個問題，然而，本題不能使用滑動窗口來解決

為什么不能使用滑動窗口？

參照示例1，其輸入的數(shù)組 nums = [4,5,0,-2,-3,1]，其中不僅有正整數(shù)，還有零和負(fù)數(shù)，

在使用滑動窗口時，當(dāng)窗口內(nèi)元素滿足條件時，要移動left指針，向前滑動窗口，但在本題中，由于有零和負(fù)整數(shù)，在窗口內(nèi)元素滿足條件時，不能移動left指針，因?yàn)橄乱粋€元素可能是零，加入后任滿足條件，也可能幾個元素相加等于0，加入后也滿足條件。因此，若是使用滑動窗口來解決本題，則會漏掉一些符合情況的子數(shù)組。

滑動窗口的思路也不行，我們繼續(xù)思考新的方法，在涉及子數(shù)組問題時，我們也常使用前綴和來解決問題

什么是前綴和？

前綴和即某序列的前n項(xiàng)和，類似于數(shù)學(xué)中的數(shù)列前n項(xiàng)和。即從首元素位置到i位置這個區(qū)間內(nèi)所有元素之和，前綴和只是一種思路，其不僅可以求和，也可以求從首元素位置到i位置區(qū)間內(nèi)的乘積等等。

我們以示例1為例子，先求前綴和數(shù)組，再通過前綴和數(shù)組來求解子數(shù)組，

然而，在這種情況下，當(dāng)我們求解子數(shù)組時，仍然需要后遍歷，求得從i到j(luò)位置的元素之和，再判斷其是否符合條件，

其時間復(fù)雜度仍是O(）

在通過前綴和數(shù)組求解子數(shù)組時，我們可以考慮向前遍歷，即i位置上的元素為到i位置的元素之和

此時，若以i位置為結(jié)尾的區(qū)間內(nèi)的元素能夠被被k整除，則

 此時dp[i] - dp[j] = mk，（m為系數(shù)），即dp[i]與dp[j]同余(dp[i]取余 k 與dp[j]取余 k 的余數(shù)相同）（兩數(shù)余數(shù)相同，在相減時就將余數(shù)消去，剩下的數(shù)便能整除k)，此時，我們只需要找到，在i位置之前有多少個前綴和元素的余數(shù)與其前綴和相同，就能夠得到以i位置為結(jié)尾的且能夠被k整除的子數(shù)組個數(shù)。

然而，在求i位置之前有多少個前綴和元素的余數(shù)與其相同時，我們還需要再向前遍歷一遍前綴和數(shù)組嗎？

我們可以使用哈希表，存儲前綴和元素的余數(shù)及其個數(shù)，這樣，便只需要計(jì)算dp[i]的余數(shù)，再從哈希表中找到相同余數(shù)的元素個數(shù)，就可知道以i位置為結(jié)尾的且能夠被k整除的子數(shù)組個數(shù)了。

在分析完思路后，我們來考慮其具體實(shí)現(xiàn)過程：

具體實(shí)現(xiàn)

首先我們需要一個哈希表，以前綴和元素模k的值為鍵，值的個數(shù)為值

// key：模k的的值，value：key的個數(shù)
Map<Integer, Integer> hash = new HashMap<>();

需要注意的是，在模k時，如果元素為負(fù)數(shù)，求出的值也為負(fù)數(shù)（例如 -4 % 5 = -4，-4 與 1 是同余的，若我們在哈希表中保存(-4, 1)，而 % i的結(jié)果為 1，并在哈希表中找到結(jié)果為1的元素個數(shù)，此時就漏掉了結(jié)果 為 -4 的情況），

因此我們需要對其進(jìn)行處理，將其變?yōu)檎龜?shù)，可以將其+k，使其變成正數(shù)，即 dp[i] % k + k（-4 + 5 = 1）；當(dāng)其為正數(shù)的時候則不需要 +k，若想要無需對元素進(jìn)行正負(fù)數(shù)判斷，則可在 +k 后再取余k，即 (dp[i] % k + k) % k，此時，若元素為正數(shù)，在 +k 后結(jié)果大于k，再對結(jié)果進(jìn)行取余，又將其變?yōu)檎_結(jié)果(（3 % 5 + 5）% 5）；若元素為負(fù)數(shù)，在 +k 后將負(fù)數(shù)變?yōu)檎龜?shù)，即正確結(jié)果，再對結(jié)果進(jìn)行取余，仍是正確結(jié)果（（-4 % 5 + 5）% 5）

求出數(shù)組的前綴和數(shù)組

由于哈希表中保存的是模k的值及其個數(shù)，因此我們不需要再創(chuàng)建一個前綴和數(shù)組用來保存前綴和，只需使用變量sum 來保存前i-1個元素的和

何時將結(jié)果放到哈希表中？

我們要從哈希表中找到相同余數(shù)的元素個數(shù)，從而知道以i位置為結(jié)尾的且能夠被k整除的子數(shù)組個數(shù)，因此哈希表中不能存放i位置之后的元素結(jié)果，因此，每遍歷一個元素，就將其結(jié)果更新到哈希表中

然而，此時還有一個細(xì)節(jié)問題

若以i位置為結(jié)尾的數(shù)組本身便能被k整除，此時模k的結(jié)果為 0，即從0位置到i位置的子數(shù)組之和能夠被k整除，則在第一次出現(xiàn)該情況時，哈希表內(nèi)沒有key = 0的元素，會漏掉該結(jié)果，因此，我們需要處理這種特殊情況，即手動將(0, 1)放入哈希表中

完整代碼

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        // key：模k的的值，value：key的個數(shù)
       Map<Integer, Integer> hash = new HashMap<>();
       //處理特殊情況
        hash.put(0,1);
        int ret = 0;//子數(shù)組的個數(shù)
        int sum = 0;//用來保存前i-1個元素之和
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
            //求出與 前i個元素之和 同余的元素個數(shù)
            int same = hash.getOrDefault((sum % k + k) % k, 0);
            ret += same;//更新結(jié)果
            hash.put((sum % k + k) % k,same + 1);//更新哈希表
        }
        return ret;
    }
}

題目來自：

974. 和可被 K 整除的子數(shù)組 - 力扣（LeetCode）

總結(jié)

到此這篇關(guān)于利用Java實(shí)現(xiàn)和可被K整除的子數(shù)組的文章就介紹到這了,更多相關(guān)Java和可被K整除的子數(shù)組內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論