其和是数组大小的倍数的最小子数组-yiteyi-C++库

给定一个大小为N的数组，我们需要找到其和可被数组大小N整除的最小子数组。 例如：

null

Input  : arr[] = [1, 1, 2, 2, 4, 2]    Output : [2 4]Size of array, N = 6    Following subarrays have sum as multiple of N[1, 1, 2, 2], [2, 4], [1, 1, 2, 2, 4, 2]The smallest among all is [2 4]

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

考虑到以下事实，我们可以解决这个问题，

Let S[i] denotes sum of first i elements i.e.     S[i] = a[1] + a[2] .. + a[i]Now subarray arr(i, i + x) has sum multiple of N then,  (arr(i] + arr[i+1] + .... + arr[i + x])) % N = 0  (S[i+x] – S[i] ) % N  = 0  S[i] % N = S[i + x] % N

我们需要找到满足上述条件的x的最小值。这可以通过使用另一个大小为N的数组modIdx以O（N）的时间复杂度在单个迭代中实现 莫迪克斯 所有元素都初始化为-1。 modIdx[k] 将在每次迭代中用i更新，其中k=sum%N。现在在每次迭代中，我们都需要更新 modIdx[k] 根据sum%N的值。我们需要检查两件事，如果在任何时刻k=0，这是我们第一次更新 modIdx[0] （即。 modIdx[0] was-1）然后我们将x指定给i+1，因为（i+1）将是子数组的长度，其和是N的倍数在另一种情况下，每当我们得到一个mod值，如果这个索引不是-1，这意味着它由另一个和值更新，其索引存储在该索引中，我们用这个差值更新x，即通过i—— modIdx[k] . 在上述每个操作之后，我们更新子阵列的最小长度值以及相应的起始索引和结束索引。最后，这为我们的问题提供了解决方案。

C++

                         // C++ program to find subarray whose sum                       
                         // is multiple of size                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Method prints smallest subarray whose sum is                       
                         // multiple of size                       
                         void                                     printSubarrayMultipleOfN(                                     int                                     arr[],                                     int                                     N)                       
                         {                       
                                                 // A direct index table to see if sum % N                       
                                                 // has appeared before or not.                       
                                                 int                                     modIdx[N];                       
           
                                                 //  initialize all mod index with -1                       
                                                 for                                     (                                     int                                     i = 0; i < N; i++)                       
                                                 modIdx[i] = -1;                       
           
                                                 // initializing minLen and curLen with larger                       
                                                 // values                       
                                                 int                                     minLen = N + 1;                       
                                                 int                                     curLen = N + 1;                       
           
                                                 // To store sum of array elements                       
                                                 int                                     sum = 0;                       
           
                                                 //  looping for each value of array                       
                                                 int                                     l, r;                       
                                                 for                                     (                                     int                                     i = 0; i < N; i++)                       
                                                 {                       
                                                 sum += arr[i];                       
                                                 sum %= N;                       
           
                                                 // If this is the first time we have                       
                                                 // got mod value as 0, then S(0, i) % N                       
                                                 // == 0                       
                                                 if                                     (modIdx[sum] == -1 && sum == 0)                       
                                                 curLen = i + 1;                       
           
                                                 // If we have reached this mod before then                       
                                                 // length of subarray will be i - previous_position                       
                                                 if                                     (modIdx[sum] != -1)                       
                                                 curLen = i - modIdx[sum];                       
           
                                                 //  choose minimum length os subarray till now                       
                                                 if                                     (curLen < minLen)                       
                                                 {                       
                                                 minLen = curLen;                       
           
                                                 //  update left and right indices of subarray                       
                                                 l = modIdx[sum] + 1;                       
                                                 r = i;                       
                                                 }                       
                                                 modIdx[sum] = i;                       
                                                 }                       
           
                                                 //  print subarray                       
                                                 for                                     (                                     int                                     i = l; i <= r; i++)                       
                                                 cout << arr[i] <<                                     " "                                     ;                       
                                                 cout << endl;                       
                         }                       
           
                         //  Driver code to test above method                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {1, 1, 2, 2, 4, 2};                       
                                                 int                                     N =                                     sizeof                                     (arr) /                                     sizeof                                     (                                     int                                     );                       
           
                                                 printSubarrayMultipleOfN(arr, N);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find subarray whose sum                       
                         // is multiple of size                       
                         class                                     GFG {                       
                                   
                                                 // Method prints smallest subarray whose sum is                       
                                                 // multiple of size                       
                                                 static                                     void                                     printSubarrayMultipleOfN(                                     int                                     arr[],                       
                                                 int                                     N)                       
                                                 {                       
                                   
                                                 // A direct index table to see if sum % N                       
                                                 // has appeared before or not.                       
                                                 int                                     modIdx[] =                                     new                                     int                                     [N];                       
           
                                                 // initialize all mod index with -1                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < N; i++)                       
                                                 modIdx[i] = -                                     1                                     ;                       
           
                                                 // initializing minLen and curLen with                       
                                                 // larger values                       
                                                 int                                     minLen = N +                                     1                                     ;                       
                                                 int                                     curLen = N +                                     1                                     ;                       
           
                                                 // To store sum of array elements                       
                                                 int                                     sum =                                     0                                     ;                       
           
                                                 // looping for each value of array                       
                                                 int                                     l =                                     0                                     , r =                                     0                                     ;                       
                                   
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < N; i++) {                       
                                                 sum += arr[i];                       
                                                 sum %= N;                       
           
                                                 // If this is the first time we                       
                                                 // have got mod value as 0, then                       
                                                 // S(0, i) % N == 0                       
                                                 if                                     (modIdx[sum] == -                                     1                                     && sum ==                                     0                                     )                       
                                                 curLen = i +                                     1                                     ;                       
           
                                                 // If we have reached this mod before                       
                                                 // then length of subarray will be i                       
                                                 // - previous_position                       
                                                 if                                     (modIdx[sum] != -                                     1                                     )                       
                                                 curLen = i - modIdx[sum];                       
           
                                                 // choose minimum length os subarray                       
                                                 // till now                       
                                                 if                                     (curLen < minLen) {                       
                                                 minLen = curLen;                       
           
                                                 // update left and right indices                       
                                                 // of subarray                       
                                                 l = modIdx[sum] +                                     1                                     ;                       
                                                 r = i;                       
                                                 }                       
                                   
                                                 modIdx[sum] = i;                       
                                                 }                       
           
                                                 // print subarray                       
                                                 for                                     (                                     int                                     i = l; i <= r; i++)                       
                                                 System.out.print(arr[i] +                                     " "                                     );                       
                                   
                                                 System.out.println();                       
                                                 }                       
                                   
                                                 // Driver program                       
                                                 public                                     static                                     void                                     main(String arg[])                       
                                                 {                       
                                                 int                                     arr[] = {                                     1                                     ,                                     1                                     ,                                     2                                     ,                                     2                                     ,                                     4                                     ,                                     2                                     };                       
                                                 int                                     N = arr.length;                       
           
                                                 printSubarrayMultipleOfN(arr, N);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Anant Agarwal.                       

Python3

                         # Python3 program to find subarray                       
                         # whose sum is multiple of size                       
           
                         # Method prints smallest subarray                       
                         # whose sum is multiple of size                       
                         def                                     printSubarrayMultipleOfN(arr, N):                       
           
                                                 # A direct index table to see if sum % N                       
                                                 # has appeared before or not.                       
                                                 modIdx                                     =                                     [                                     0                                     for                                     i                                     in                                     range                                     (N)]                       
           
                                                 # initialize all mod index with -1                       
                                                 for                                     i                                     in                                     range                                     (N):                       
                                                 modIdx[i]                                     =                                     -                                     1                       
           
                                                 # initializing minLen and curLen                       
                                                 # with larger values                       
                                                 minLen                                     =                                     N                                     +                                     1                       
                                                 curLen                                     =                                     N                                     +                                     1                       
           
                                                 # To store sum of array elements                       
                                                 sum                                     =                                     0                       
           
                                                 # looping for each value of array                       
                                                 l                                     =                                     0                                     ; r                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (N):                       
                                   
                                                 sum                                     +                                     =                                     arr[i]                       
                                                 sum                                     %                                     =                                     N                       
           
                                                 # If this is the first time we have                       
                                                 # got mod value as 0, then S(0, i) % N                       
                                                 # == 0                       
                                                 if                                     (modIdx[                                     sum                                     ]                                     =                                     =                                     -                                     1                                     and                                     sum                                     =                                     =                                     0                                     ):                       
                                                 curLen                                     =                                     i                                     +                                     1                       
           
                                                 # If we have reached this mod before then                       
                                                 # length of subarray will be i - previous_position                       
                                                 if                                     (modIdx[                                     sum                                     ] !                                     =                                     -                                     1                                     ):                       
                                                 curLen                                     =                                     i                                     -                                     modIdx[                                     sum                                     ]                       
           
                                                 # choose minimum length os subarray till now                       
                                                 if                                     (curLen < minLen):                       
                                   
                                                 minLen                                     =                                     curLen                       
           
                                                 # update left and right indices of subarray                       
                                                 l                                     =                                     modIdx[                                     sum                                     ]                                     +                                     1                       
                                                 r                                     =                                     i                       
                                   
                                                 modIdx[                                     sum                                     ]                                     =                                     i                       
                                   
                                                 # print subarray                       
                                                 for                                     i                                     in                                     range                                     (l, r                                     +                                     1                                     ):                       
                                                 print                                     (arr[i] ,                                     " "                                     , end                                     =                                     "")                       
                                                 print                                     ()                       
           
                         # Driver program                       
                         arr                                     =                                     [                                     1                                     ,                                     1                                     ,                                     2                                     ,                                     2                                     ,                                     4                                     ,                                     2                                     ]                       
                         N                                     =                                     len                                     (arr)                       
                         printSubarrayMultipleOfN(arr, N)                       
           
                         # This code is contributed by Anant Agarwal.                       

C#

                         // C# program to find subarray whose sum                       
                         // is multiple of size                       
                         using                                     System;                       
                         class                                     GFG {                       
                                   
                                                 // Method prints smallest subarray whose sum is                       
                                                 // multiple of size                       
                                                 static                                     void                                     printSubarrayMultipleOfN(                                     int                                     []arr,                       
                                                 int                                     N)                       
                                                 {                       
                                   
                                                 // A direct index table to see if sum % N                       
                                                 // has appeared before or not.                       
                                                 int                                     []modIdx =                                     new                                     int                                     [N];                       
           
                                                 // initialize all mod index with -1                       
                                                 for                                     (                                     int                                     i = 0; i < N; i++)                       
                                                 modIdx[i] = -1;                       
           
                                                 // initializing minLen and curLen with                       
                                                 // larger values                       
                                                 int                                     minLen = N + 1;                       
                                                 int                                     curLen = N + 1;                       
           
                                                 // To store sum of array elements                       
                                                 int                                     sum = 0;                       
           
                                                 // looping for each value of array                       
                                                 int                                     l = 0, r = 0;                       
                                   
                                                 for                                     (                                     int                                     i = 0; i < N; i++) {                       
                                                 sum += arr[i];                       
                                                 sum %= N;                       
           
                                                 // If this is the first time we                       
                                                 // have got mod value as 0, then                       
                                                 // S(0, i) % N == 0                       
                                                 if                                     (modIdx[sum] == -1 && sum == 0)                       
                                                 curLen = i + 1;                       
           
                                                 // If we have reached this mod before                       
                                                 // then length of subarray will be i                       
                                                 // - previous_position                       
                                                 if                                     (modIdx[sum] != -1)                       
                                                 curLen = i - modIdx[sum];                       
           
                                                 // choose minimum length os subarray                       
                                                 // till now                       
                                                 if                                     (curLen < minLen) {                       
                                                 minLen = curLen;                       
           
                                                 // update left and right indices                       
                                                 // of subarray                       
                                                 l = modIdx[sum] + 1;                       
                                                 r = i;                       
                                                 }                       
                                   
                                                 modIdx[sum] = i;                       
                                                 }                       
           
                                                 // print subarray                       
                                                 for                                     (                                     int                                     i = l; i <= r; i++)                       
                                                 Console.Write(arr[i] +                                     " "                                     );                       
                                   
                                                 Console.WriteLine();                       
                                                 }                       
                                   
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     []arr = {1, 1, 2, 2, 4, 2};                       
                                                 int                                     N = arr.Length;                       
           
                                                 printSubarrayMultipleOfN(arr, N);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by nitin mittal.                       

PHP

                         <?php                       
                         // PHP program to find subarray                       
                         // whose sum is multiple of size                       
           
                         // Method prints smallest subarray                       
                         // whose sum is multiple of size                       
                         function                                     printSubarrayMultipleOfN(                                     $arr                                     ,                       
                                                 $N                                     )                       
                         {                       
                                                 // A direct index table to see                       
                                                 // if sum % N has appeared                       
                                                 // before or not.                       
                                                 $modIdx                                     =                                     array                                     ();                       
           
                                                 // initialize all mod                       
                                                 // index with -1                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $N                                     ;                                     $i                                     ++)                       
                                                 $modIdx                                     [                                     $i                                     ] = -1;                       
           
                                                 // initializing minLen and                       
                                                 // curLen with larger values                       
                                                 $minLen                                     =                                     $N                                     + 1;                       
                                                 $curLen                                     =                                     $N                                     + 1;                       
           
                                                 // To store sum of                       
                                                 // array elements                       
                                                 $sum                                     = 0;                       
           
                                                 // looping for each                       
                                                 // value of array                       
                                                 $l                                     ;                                     $r                                     ;                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $N                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 $sum                                     +=                                     $arr                                     [                                     $i                                     ];                       
                                                 $sum                                     %=                                     $N                                     ;                       
           
                                                 // If this is the first time                       
                                                 // we have got mod value as 0,                       
                                                 // then S(0, i) % N == 0                       
                                                 if                                     (                                     $modIdx                                     [                                     $sum                                     ] == -1 &&                       
                                                 $sum                                     == 0)                       
                                                 $curLen                                     =                                     $i                                     + 1;                       
           
                                                 // If we have reached this mod                       
                                                 // before then length of subarray                       
                                                 // will be i - previous_position                       
                                                 if                                     (                                     $modIdx                                     [                                     $sum                                     ] != -1)                       
                                                 $curLen                                     =                                     $i                                     -                                     $modIdx                                     [                                     $sum                                     ];                       
           
                                                 // choose minimum length                       
                                                 // as subarray till now                       
                                                 if                                     (                                     $curLen                                     <                                     $minLen                                     )                       
                                                 {                       
                                                 $minLen                                     =                                     $curLen                                     ;                       
           
                                                 // update left and right                       
                                                 // indices of subarray                       
                                                 $l                                     =                                     $modIdx                                     [                                     $sum                                     ] + 1;                       
                                                 $r                                     =                                     $i                                     ;                       
                                                 }                       
                                                 $modIdx                                     [                                     $sum                                     ] =                                     $i                                     ;                       
                                                 }                       
           
                                                 // print subarray                       
                                                 for                                     (                                     $i                                     =                                     $l                                     ;                                     $i                                     <=                                     $r                                     ;                                     $i                                     ++)                       
                                                 echo                                     $arr                                     [                                     $i                                     ] ,                                     " "                                     ;                       
                                                 echo                                     ""                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $arr                                     =                                     array                                     (1, 1, 2, 2, 4, 2);                       
                         $N                                     =                                     count                                     (                                     $arr                                     );                       
           
                         printSubarrayMultipleOfN(                                     $arr                                     ,                                     $N                                     );                       
           
                         // This code is contributed by anuj_67.                       
                         ?>                       

Javascript

                         <script>                       
           
                                                 // Javascript program to find subarray whose sum                       
                                                 // is multiple of size                       
                                   
                                                 // Method prints smallest subarray whose sum is                       
                                                 // multiple of size                       
                                                 function                                     printSubarrayMultipleOfN(arr, N)                       
                                                 {                       
                                   
                                                 // A direct index table to see if sum % N                       
                                                 // has appeared before or not.                       
                                                 let modIdx =                                     new                                     Array(N);                       
                                   
                                                 // initialize all mod index with -1                       
                                                 for                                     (let i = 0; i < N; i++)                       
                                                 modIdx[i] = -1;                       
                                   
                                                 // initializing minLen and curLen with                       
                                                 // larger values                       
                                                 let minLen = N + 1;                       
                                                 let curLen = N + 1;                       
                                   
                                                 // To store sum of array elements                       
                                                 let sum = 0;                       
                                   
                                                 // looping for each value of array                       
                                                 let l = 0, r = 0;                       
                                   
                                                 for                                     (let i = 0; i < N; i++) {                       
                                                 sum += arr[i];                       
                                                 sum %= N;                       
                                   
                                                 // If this is the first time we                       
                                                 // have got mod value as 0, then                       
                                                 // S(0, i) % N == 0                       
                                                 if                                     (modIdx[sum] == -1 && sum == 0)                       
                                                 curLen = i + 1;                       
                                   
                                                 // If we have reached this mod before                       
                                                 // then length of subarray will be i                       
                                                 // - previous_position                       
                                                 if                                     (modIdx[sum] != -1)                       
                                                 curLen = i - modIdx[sum];                       
                                   
                                                 // choose minimum length os subarray                       
                                                 // till now                       
                                                 if                                     (curLen < minLen) {                       
                                                 minLen = curLen;                       
                                   
                                                 // update left and right indices                       
                                                 // of subarray                       
                                                 l = modIdx[sum] + 1;                       
                                                 r = i;                       
                                                 }                       
                                   
                                                 modIdx[sum] = i;                       
                                                 }                       
                                   
                                                 // print subarray                       
                                                 for                                     (let i = l; i <= r; i++)                       
                                                 document.write(arr[i] +                                     " "                                     );                       
                                   
                                                 document.write(                                     "</br>"                                     );                       
                                                 }                       
                                   
                                                 let arr = [1, 1, 2, 2, 4, 2];                       
                                                 let N = arr.length;                       
           
                                                 printSubarrayMultipleOfN(arr, N);                       
                                   
                         </script>                       

输出：

2 4

本文由 乌特卡什·特里维迪 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章