將數組分成兩部分,總和可被K整除


難度級別 容易獎學金
經常問 亞馬遜 Microsoft微軟
排列 哈希

將數組劃分為成對可被K整除的對是一個問題,時不時要進行各種調整。 那些了解我的人都知道我習慣將這些問題轉換為故事。 在本文中,讓我們研究這個問題。

理解問題的情況

隨著大流行的蔓延,我們有許多組織加緊為窮人提供幫助和救濟。 今天,我們是這些救濟工作的協調者。 我們負有收集口糧袋並將其分成“ k”袋的任務。 我們從每個家庭獲得的口糧以陣列的形式表示。 為了更好的理解。 讓我們看一個示例測試用例,以更加清楚。

輸入:

5

A = [4,5,0,-2,-3,1]

輸出:

7

被5整除的子數組的數量為:

[4,5,0,-2,-3,1],[5],[5,0],[5,0,-2,-3],[0],[0,-2,-3],[-2,-3]

該數組代表了我們從每個家庭獲得的數據包數量。 我們將附近的家庭聚在一起,以將k個小包運送到最近的位置。 更容易地,我們正在尋求將數組劃分為子數組, 總和 到“ k”。我們可以考慮各種解決問題的方法。 但是,在這篇文章中,我將介紹最容易理解的最簡單的方法。

將數組與K整除的成對算法

  • 我們將創建一個數組,該數組保存了上述索引的總和
  • 然後,當總和除以索引時,我們找到了直到該索引為止的餘數
  • 如果餘數小於0,我們加k
  • Hashmap將剩餘的和它的出現作為鍵值對存儲
  • 然後,我們將使用來查找每個餘數可以創建的子集數
  • 總和=總和+值*(值-1)/ 2

圖片說明了該過程可以

將數組分成兩部分,總和可被K整除
問題說明

現在,我們掌握瞭如何做的事情,讓我們研究一下代碼

Java代碼

class Solution 
{
    public int subarraysDivByK(int[] A, int k) 
    {
        if(A==null || A.length<1)
            return -1;
        int sum[]=new int[A.length+1];
        for(int i=1;i<sum.length;i++)
        {
            sum[i]=sum[i-1]+A[i-1];
        }
        HashMap<Integer,Integer>combos=new HashMap<Integer,Integer>();
        for(int i=0;i<sum.length;i++)
        {
            int cur=sum[i]%k;
            if(cur<0)
                cur=cur+k;
            if(!combos.containsKey(cur))
                combos.put(cur,1);
            else
                combos.put(cur,combos.get(cur)+1);
        }
        System.out.println(combos);
        int ans=0;
        for(int i:combos.values())
        {
            ans+=i*(i-1)/2;
        }
        return ans;
    }
}

C ++代碼

class Solution 
{
public:
    int subarraysDivByK(vector<int>& A, int k) 
    {
     if(A.size()<1)
            return -1;
        int sum[A.size()+1];
        for(int i=1;i<A.size()+1;i++)
        {
            sum[i]=sum[i-1]+A[i-1];
        }
        unordered_map<int,int>combos;
        for(int i=0;i<A.size()+1;i++)
        {
            int cur=sum[i]%k;
            if(cur<0)
                cur=cur+k;
            combos[cur]+=1;
        }
        int ans=0;
        for(auto i:combos)
        {
            ans+=(i.second)*(i.second-1)/2;
        }
        return ans;    
    }
};
5
{4, 5, 0, -2, -3, 1}
7

將數組劃分為成對可被K整除的對的複雜度分析

在此解決方案中,該問題的時間複雜度和空間複雜度可以列為:

時間複雜度= O(n)

空間複雜度= O(n)

怎麼樣?

首先是空間複雜性

  • 由N個條目組成的HashMap具有所有值
  • 該地圖與我們擁有的剩餘數量一樣大
  • 總之,這導致空間複雜度達到O(n)

其次,時間複雜度

  • 我們在解決方案中運行了三個循環
  • 首先,找到總和= O(n)的循環
  • 其次,找到餘數= O(n)的循環
  • 第三找到所有組合= O(餘數)
  • 總之,所有這些都導致​​了O(n)的時間複雜性

參考