和可被k整除的最长子阵-yiteyi-C++库

给予 arr[] 包含 N 整数和正整数 K 问题是找出最长子阵的长度，其元素之和可被给定值整除 K . 例如：

null

Input : arr[] = {2, 7, 6, 1, 4, 5}, k = 3Output : 4The subarray is {7, 6, 1, 4} with sum 18,which is divisible by 3.Input : arr[] = {-2, 2, -5, 12, -11, -1, 7}Output : 5

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

方法1（天真的方法）： 考虑所有子数组并返回子数组的长度和可整除 K 长度最长。时间复杂度：O（n） ^2. ). 方法2（有效方法）： 创建一个数组 mod_arr[] 哪里 mod_arr[i] 商店 （总和（arr[0]+arr[1]..+arr[i]）%k） .创建一个哈希表，将元组作为 （ele，idx） 哪里埃勒代表了 mod_arr[] 和 idx 表示元素在中首次出现的索引 mod_arr[] .现在，特拉弗斯 mod_arr[] 从i=0到n，并遵循下面给出的步骤。

如果mod_arr[i]==0，则更新 麦克斯伦 =（i+1）。
否则，如果哈希表中不存在mod_arr[i]，则创建元组 （mod_arr[i]，i） 在哈希表中。
否则，获取与 mod_arr[i] 在哈希表中。就这样吧 idx .
如果maxLen 麦克斯伦 =（i–idx）。

终于回来了 麦克斯伦 .

C++

                         // C++ implementation to find the longest subarray                       
                         // with sum divisible by k                       
                         #include <bits/stdc++.h>                       
           
                         using                                     namespace                                     std;                       
           
                         // function to find the longest subarray                       
                         // with sum divisible by k                       
                         int                                     longSubarrWthSumDivByK(                                     int                                     arr[],                       
                                                 int                                     n,                                     int                                     k)                       
                         {                       
                                                 // unordered map 'um' implemented as                       
                                                 // hash table                       
                                                 unordered_map<                                     int                                     ,                                     int                                     > um;                       
                                   
                                                 // 'mod_arr[i]' stores (sum[0..i] % k)                       
                                                 int                                     mod_arr[n], max = 0;                       
                                                 int                                     curr_sum = 0;                       
                                   
                                                 // traverse arr[] and build up the                       
                                                 // array 'mod_arr[]'                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 curr_sum += arr[i];                       
                                   
                                                 // as the sum can be negative, taking modulo twice                       
                                                 mod_arr[i] = ((curr_sum % k) + k) % k;                       
                                                 }                       
                                   
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 // if true then sum(0..i) is divisible                       
                                                 // by k                       
                                                 if                                     (mod_arr[i] == 0)                       
                                                 // update 'max'                       
                                                 max = i + 1;                       
                                   
                                                 // if value 'mod_arr[i]' not present in 'um'                       
                                                 // then store it in 'um' with index of its                       
                                                 // first occurrence                       
                                                 else                                     if                                     (um.find(mod_arr[i]) == um.end())                       
                                                 um[mod_arr[i]] = i;                       
                                   
                                                 else                       
                                                 // if true, then update 'max'                       
                                                 if                                     (max < (i - um[mod_arr[i]]))                       
                                                 max = i - um[mod_arr[i]];                       
                                                 }                       
                                   
                                                 // required length of longest subarray with                       
                                                 // sum divisible by 'k'                       
                                                 return                                     max;                       
                         }                       
           
                         // Driver program to test above                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {2, 7, 6, 1, 4, 5};                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 int                                     k = 3;                       
                                   
                                                 cout <<                                     "Length = "                       
                                                 << longSubarrWthSumDivByK(arr, n, k);                       
                                   
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java implementation to find the longest                       
                         // subarray with sum divisible by k                       
                         import                                     java.io.*;                       
                         import                                     java.util.*;                       
           
                         class                                     GfG {                       
                                   
                                                 // function to find the longest subarray                       
                                                 // with sum divisible by k                       
                                                 static                                     int                                     longSubarrWthSumDivByK(                                     int                                     arr[],                       
                                                 int                                     n,                                     int                                     k)                       
                                                 {                       
                                                 // unordered map 'um' implemented as                       
                                                 // hash table                       
                                                 HashMap<Integer, Integer> um=                                     new                                     HashMap<Integer, Integer>();                       
                                   
                                                 // 'mod_arr[i]' stores (sum[0..i] % k)                       
                                                 int                                     mod_arr[]=                                     new                                     int                                     [n];                       
                                                 int                                     max =                                     0                                     ;                       
                                                 int                                     curr_sum =                                     0                                     ;                       
                                   
                                                 // traverse arr[] and build up the                       
                                                 // array 'mod_arr[]'                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 {                       
                                                 curr_sum += arr[i];                       
                                   
                                                 // as the sum can be negative,                       
                                                 // taking modulo twice                       
                                                 mod_arr[i] = ((curr_sum % k) + k) % k;                       
                                                 }                       
                                   
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 {                       
                                                 // if true then sum(0..i) is                       
                                                 // divisible by k                       
                                                 if                                     (mod_arr[i] ==                                     0                                     )                       
                                                 // update 'max'                       
                                                 max = i +                                     1                                     ;                       
                                   
                                                 // if value 'mod_arr[i]' not present in 'um'                       
                                                 // then store it in 'um' with index of its                       
                                                 // first occurrence                       
                                                 else                                     if                                     (um.containsKey(mod_arr[i]) ==                                     false                                     )                       
                                                 um.put(mod_arr[i] , i);                       
                                   
                                                 else                       
                                                 // if true, then update 'max'                       
                                                 if                                     (max < (i - um.get(mod_arr[i])))                       
                                                 max = i - um.get(mod_arr[i]);                       
                                                 }                       
                                   
                                                 // required length of longest subarray with                       
                                                 // sum divisible by 'k'                       
                                                 return                                     max;                       
                                                 }                       
                                   
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     2                                     ,                                     7                                     ,                                     6                                     ,                                     1                                     ,                                     4                                     ,                                     5                                     };                       
                                                 int                                     n = arr.length;                       
                                                 int                                     k =                                     3                                     ;                       
                                   
                                                 System.out.println(                                     "Length = "                                     +                       
                                                 longSubarrWthSumDivByK(arr, n, k));                       
                                   
                                                 }                       
                         }                       
           
                         // This code is contributed by Gitanjali.                       

Python3

                         # Python3 implementation to find the                       
                         # longest subarray with sum divisible by k                       
           
                         # Function to find the longest                       
                         # subarray with sum divisible by k                       
                         def                                     longSubarrWthSumDivByK(arr, n, k):                       
                                   
                                                 # unordered map 'um' implemented                       
                                                 # as hash table                       
                                                 um                                     =                                     {}                       
           
                                                 # 'mod_arr[i]' stores (sum[0..i] % k)                       
                                                 mod_arr                                     =                                     [                                     0                                     for                                     i                                     in                                     range                                     (n)]                       
                                                 max                                     =                                     0                       
                                                 curr_sum                                     =                                     0                       
                                   
                                                 # Traverse arr[] and build up                       
                                                 # the array 'mod_arr[]'                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 curr_sum                                     +                                     =                                     arr[i]                       
                                   
                                                 # As the sum can be negative,                       
                                                 # taking modulo twice                       
                                                 mod_arr[i]                                     =                                     ((curr_sum                                     %                                     k)                                     +                                     k)                                     %                                     k                       
                                   
                                                 for                                     i                                     in                                     range                                     (n):                       
                                   
                                                 # If true then sum(0..i) is                       
                                                 # divisible by k                       
                                                 if                                     (mod_arr[i]                                     =                                     =                                     0                                     ):                       
                                   
                                                 # Update 'max'                       
                                                 max                                     =                                     i                                     +                                     1                       
                                   
                                                 # If value 'mod_arr[i]' not present in                       
                                                 # 'um' then store it in 'um' with index                       
                                                 # of its first occurrence                       
                                                 elif                                     (mod_arr[i]                                     not                                     in                                     um):                       
                                                 um[mod_arr[i]]                                     =                                     i                       
                                   
                                                 else                                     :                       
                                   
                                                 # If true, then update 'max'                       
                                                 if                                     (                                     max                                     < (i                                     -                                     um[mod_arr[i]])):                       
                                                 max                                     =                                     i                                     -                                     um[mod_arr[i]]                       
                                   
                                                 # Required length of longest subarray                       
                                                 # with sum divisible by 'k'                       
                                                 return                                     max                       
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                   
                                                 arr                                     =                                     [                                     2                                     ,                                     7                                     ,                                     6                                     ,                                     1                                     ,                                     4                                     ,                                     5                                     ]                       
                                                 n                                     =                                     len                                     (arr)                       
                                                 k                                     =                                     3                       
                                   
                                                 print                                     (                                     "Length ="                                     ,                       
                                                 longSubarrWthSumDivByK(arr, n, k))                       
                                   
                         # This code is contributed by                       
                         # Surendra_Gangwar                       

C#

                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         // C# implementation to find the longest                       
                         // subarray with sum divisible by k                       
           
                         public                                     class                                     GfG                       
                         {                       
           
                                                 // function to find the longest subarray                       
                                                 // with sum divisible by k                       
                                                 public                                     static                                     int                                     longSubarrWthSumDivByK(                                     int                                     [] arr,                                     int                                     n,                                     int                                     k)                       
                                                 {                       
                                                 // unordered map 'um' implemented as                       
                                                 // hash table                       
                                                 Dictionary<                                     int                                     ,                                     int                                     > um =                                     new                                     Dictionary<                                     int                                     ,                                     int                                     >();                       
           
                                                 // 'mod_arr[i]' stores (sum[0..i] % k)                       
                                                 int                                     [] mod_arr =                                     new                                     int                                     [n];                       
                                                 int                                     max = 0;                       
                                                 int                                     curr_sum = 0;                       
           
                                                 // traverse arr[] and build up the                       
                                                 // array 'mod_arr[]'                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 curr_sum += arr[i];                       
           
                                                 // as the sum can be negative,                       
                                                 // taking modulo twice                       
                                                 mod_arr[i] = ((curr_sum % k) + k) % k;                       
                                                 }                       
           
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 // if true then sum(0..i) is                       
                                                 // divisible by k                       
                                                 if                                     (mod_arr[i] == 0)                       
                                                 {                       
                                                 // update 'max'                       
                                                 max = i + 1;                       
                                                 }                       
           
                                                 // if value 'mod_arr[i]' not present in 'um'                       
                                                 // then store it in 'um' with index of its                       
                                                 // first occurrence                       
                                                 else                                     if                                     (um.ContainsKey(mod_arr[i]) ==                                     false                                     )                       
                                                 {                       
                                                 um[mod_arr[i]] = i;                       
                                                 }                       
           
                                                 else                       
                                                 {                       
                                                 // if true, then update 'max'                       
                                                 if                                     (max < (i - um[mod_arr[i]]))                       
                                                 {                       
                                                 max = i - um[mod_arr[i]];                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // required length of longest subarray with                       
                                                 // sum divisible by 'k'                       
                                                 return                                     max;                       
                                                 }                       
           
                                                 public                                     static                                     void                                     Main(                                     string                                     [] args)                       
                                                 {                       
                                                 int                                     [] arr =                                     new                                     int                                     [] {2, 7, 6, 1, 4, 5};                       
                                                 int                                     n = arr.Length;                       
                                                 int                                     k = 3;                       
           
                                                 Console.WriteLine(                                     "Length = "                                     + longSubarrWthSumDivByK(arr, n, k));                       
           
                                                 }                       
                         }                       
           
                         // This code is contributed by Shrikant13                       

Javascript

                         <script>                       
           
                         // Javascript implementation to find the longest subarray                       
                         // with sum divisible by k                       
           
                         // function to find the longest subarray                       
                         // with sum divisible by k                       
                         function                                     longSubarrWthSumDivByK(arr,  n, k)                       
                         {                       
                                                 // unordered map 'um' implemented as                       
                                                 // hash table                       
                                                 var                                     um =                                     new                                     Map();                       
                                   
                                                 // 'mod_arr[i]' stores (sum[0..i] % k)                       
                                                 var                                     mod_arr = Array(n), max = 0;                       
                                                 var                                     curr_sum = 0;                       
                                   
                                                 // traverse arr[] and build up the                       
                                                 // array 'mod_arr[]'                       
                                                 for                                     (                                     var                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 curr_sum += arr[i];                       
                                   
                                                 // as the sum can be negative, taking modulo twice                       
                                                 mod_arr[i] = ((curr_sum % k) + k) % k;                       
                                                 }                       
                                   
                                                 for                                     (                                     var                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 // if true then sum(0..i) is divisible                       
                                                 // by k                       
                                                 if                                     (mod_arr[i] == 0)                       
                                                 // update 'max'                       
                                                 max = i + 1;                       
                                   
                                                 // if value 'mod_arr[i]' not present in 'um'                       
                                                 // then store it in 'um' with index of its                       
                                                 // first occurrence                       
                                                 else                                     if                                     (!um.has(mod_arr[i]))                       
                                                 um.set(mod_arr[i] , i);                       
                                   
                                                 else                       
                                                 // if true, then update 'max'                       
                                                 if                                     (max < (i - um.get(mod_arr[i])))                       
                                                 max = i - um.get(mod_arr[i]);                       
                                                 }                       
                                   
                                                 // required length of longest subarray with                       
                                                 // sum divisible by 'k'                       
                                                 return                                     max;                       
                         }                       
           
                         // Driver program to test above                       
                         var                                     arr = [2, 7, 6, 1, 4, 5];                       
                         var                                     n = arr.length;                       
                         var                                     k = 3;                       
           
                         document.write(                                     "Length = "                       
                                                 + longSubarrWthSumDivByK(arr, n, k));                       
                                   
                         // This code is contributed by rrrtnx.                       
                         </script>                       

输出

Length = 4

时间复杂度：O（n）。辅助空间：O（n^2）。该方法的时间复杂度可以通过使用大小等于k的数组进行O（1）查找来提高，因为对输入数组的元素使用模运算后，所有元素都将小于k。

空间优化 对于上述方法—— O（N）

我们不是保留一个单独的数组来存储所有值的模，而是在填充hashmap时进行计算。

C++

                         #include <bits/stdc++.h>                       
           
                         using                                     namespace                                     std;                       
           
                         // function to find the longest subarray                       
                         // with sum divisible by k                       
                         int                                     longSubarrWthSumDivByK(                                     int                                     arr[],                                     int                                     n,                                     int                                     k)                       
                         {                       
                                                 // unordered map 'um' implemented as                       
                                                 // hash table                       
                                                 unordered_map<                                     int                                     ,                                     int                                     > um;                       
           
                                                 // 'mod_arr[i]' stores (sum[0..i] % k)                       
                                                 int                                     max = 0;                       
                                                 int                                     curr_sum = 0;                       
           
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 curr_sum += arr[i];                       
           
                                                 int                                     mod = ((curr_sum % k) + k) % k;                       
                                                 // if true then sum(0..i) is divisible                       
                                                 // by k                       
                                                 if                                     (mod == 0)                       
                                                 // update 'max'                       
                                                 max = i + 1;                       
           
                                                 // if value 'mod_arr[i]' not present in 'um'                       
                                                 // then store it in 'um' with index of its                       
                                                 // first occurrence                       
                                                 else                                     if                                     (um.find(mod) == um.end())                       
                                                 um[mod] = i;                       
           
                                                 else                       
                                                 // if true, then update 'max'                       
                                                 if                                     (max < (i - um[mod]))                       
                                                 max = i - um[mod];                       
                                                 }                       
           
                                                 // required length of longest subarray with                       
                                                 // sum divisible by 'k'                       
                                                 return                                     max;                       
                         }                       
           
                         // Driver program to test above                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 2, 7, 6, 1, 4, 5 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 int                                     k = 3;                       
           
                                                 cout <<                                     "Length = "                       
                                                 << longSubarrWthSumDivByK(arr, n, k);                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         /*package whatever //do not write package name here */                       
           
                         import                                     java.io.*;                       
                         import                                     java.util.*;                       
           
                         class                                     GFG {                       
                                                 static                                     int                                     longSubarrWthSumDivByK(                                     int                                     arr[],                                     int                                     n,                       
                                                 int                                     k)                       
                                                 {                       
                                                 // Complete the function                       
                                                 Map<Integer, Integer> map =                                     new                                     HashMap<>();                       
                                                 int                                     max =                                     0                                     ;                       
           
                                                 int                                     sum =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++) {                       
                                                 sum += arr[i];                       
                                                 // to handle negavtive values as well                       
                                                 int                                     mod = ((sum % k) + k) % k;                       
           
                                                 // this will be the longest possible length from                       
                                                 // start                       
                                                 if                                     (mod ==                                     0                                     )                       
                                                 max = i +                                     1                                     ;                       
           
                                                 if                                     (!map.containsKey(mod))                       
                                                 map.put(mod, i);                       
                                                 else                                     {                       
                                                 int                                     sz = i - map.get(mod);                       
                                                 max = Math.max(max, sz);                       
                                                 }                       
                                                 }                       
           
                                                 return                                     max;                       
                                                 }                       
           
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     2                                     ,                                     7                                     ,                                     6                                     ,                                     1                                     ,                                     4                                     ,                                     5                                     };                       
                                                 int                                     n = arr.length;                       
                                                 int                                     k =                                     3                                     ;                       
           
                                                 System.out.println(                       
                                                 "Length = "                       
                                                 + longSubarrWthSumDivByK(arr, n, k));                       
                                                 }                       
                         }                       

Python3

                         # function to find the longest subarray                       
                         #  with sum divisible by k                       
                         def                                     longSubarrWthSumDivByK(arr, n, k):                       
                                   
                                                 # unordered map 'um' implemented as                       
                                                 # hash table                       
                                                 um                                     =                                     {}                       
           
                                                 # 'mod_arr[i]' stores (sum[0..i] % k)                       
                                                 max                                     =                                     0                       
                                                 curr_sum                                     =                                     0                       
           
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , n):                       
                                                 curr_sum                                     +                                     =                                     arr[i]                       
                                                 mod                                     =                                     ((curr_sum                                     %                                     k)                                     +                                     k)                                     %                                     k                       
                                                 # if true then sum(0..i) is divisible by k                       
                                                 if                                     mod                                     =                                     =                                     0                                     :                       
                                                 # update 'max'                       
                                                 max                                     =                                     i                                     +                                     1                       
                                   
                                                 # if value 'mod_arr[i]' not present in 'um'                       
                                                 # then store it in 'um' with index of its                       
                                                 # first occurrence                       
                                                 elif                                     mod                                     in                                     um.keys():                       
                                                 if                                     max                                     < (i                                     -                                     um[mod]):                       
                                                 max                                     =                                     i                                     -                                     um[mod]                       
           
                                                 else                                     :                       
                                                 um[mod]                                     =                                     i                       
           
                                                 # required length of longest subarray with                       
                                                 # sum divisible by 'k'                       
                                                 return                                     max                       
                                   
                         arr                                     =                                     [                                     2                                     ,                                     7                                     ,                                     6                                     ,                                     1                                     ,                                     4                                     ,                                     5                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         k                                     =                                     3                       
                         print                                     (longSubarrWthSumDivByK(arr, n, k))                       
           
                         # This code is contributed by amreshkumar3.                       

Javascript

                         <script>                       
                         // function to find the longest subarray                       
                         // with sum divisible by k                       
                         function                                     longSubarrWthSumDivByK(arr,n,k)                       
                         {                       
                                                 // map 'um' implemented as                       
                                                 // hash table                       
                                                 let um =                                     new                                     Map();                       
           
                                                 // 'mod_arr[i]' stores (sum[0..i] % k)                       
                                                 let max = 0;                       
                                                 let curr_sum = 0;                       
           
                                                 for                                     (let i = 0; i < n; i++) {                       
                                                 curr_sum += arr[i];                       
           
                                                 let mod = ((curr_sum % k) + k) % k;                       
                                                 // if true then sum(0..i) is divisible                       
                                                 // by k                       
                                                 if                                     (mod == 0)                       
                                                 // update 'max'                       
                                                 max = i + 1;                       
           
                                                 // if value 'mod_arr[i]' not present in 'um'                       
                                                 // then store it in 'um' with index of its                       
                                                 // first occurrence                       
                                                 else                                     if                                     (um.has(mod) ==                                     false                                     )                       
                                                 um.set(mod,i);                       
           
                                                 else                       
                                                 // if true, then update 'max'                       
                                                 if                                     (max < (i - um.get(mod)))                       
                                                 max = i - um.get(mod);                       
                                                 }                       
           
                                                 // required length of longest subarray with                       
                                                 // sum divisible by 'k'                       
                                                 return                                     max;                       
                         }                       
           
                         // Driver program to test above                       
           
                         let arr = [ 2, 7, 6, 1, 4, 5 ];                       
                         let n = arr.length;                       
                         let k = 3;                       
           
                         document.write(                                     "Length = "                                     +longSubarrWthSumDivByK(arr, n, k));                       
           
                         // This code is contributed by shinjanpatra.                       
                         </script>                       

输出

Length = 4

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章