快捷導(dǎo)航

利用Java實(shí)現(xiàn)和可被K整除的子數(shù)組完整實(shí)例

更新時(shí)間：2024年01月23日 11:17:52 作者：楠枬

這篇文章主要給大家介紹了關(guān)于利用Java實(shí)現(xiàn)和可被K整除的子數(shù)組的相關(guān)資料,這道題來自力扣,通過學(xué)習(xí)這道題的解題思路以及代碼對(duì)大家的學(xué)習(xí)或者工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下

一、題目描述

給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(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ù)組，在遍歷每個(gè)元素的同時(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;
    }
}

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

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

為什么不能使用滑動(dòng)窗口？

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

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

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

什么是前綴和？

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

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

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

其時(shí)間復(fù)雜度仍是O( $N^{2}$ ）

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

$N^{2}$

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

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

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

我們可以使用哈希表，存儲(chǔ)前綴和元素的余數(shù)及其個(gè)數(shù)，這樣，便只需要計(jì)算dp[i]的余數(shù)，再?gòu)墓１碇姓业较嗤鄶?shù)的元素個(gè)數(shù)，就可知道以i位置為結(jié)尾的且能夠被k整除的子數(shù)組個(gè)數(shù)了。

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

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

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

// key：模k的的值，value：key的個(gè)數(shù)
Map&lt;Integer, Integer&gt; hash = new HashMap&lt;&gt;();

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

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

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

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

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

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

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

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

完整代碼

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        // key：模k的的值，value：key的個(gè)數(shù)
       Map<Integer, Integer> hash = new HashMap<>();
       //處理特殊情況
        hash.put(0,1);
        int ret = 0;//子數(shù)組的個(gè)數(shù)
        int sum = 0;//用來保存前i-1個(gè)元素之和
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
            //求出與 前i個(gè)元素之和 同余的元素個(gè)數(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）