算法题：最长子数组，元素总和不超过k

本文概述

• C ++
• Java
• Python3
• C#
• 的PHP

给定一个整数数组, 我们的目标是找到最大子数组的长度, 该子数组的元素之和最多为"k", 其中k> 0。

例子：

Input : arr[] = {1, 2, 1, 0, 1, 1, 0}, k = 4
Output : 5
Explanation:
 {1, 2, 1} => sum = 4, length = 3
 {1, 2, 1, 0}, {2, 1, 0, 1} => sum = 4, length = 4
 {1, 0, 1, 1, 0} =>5 sum = 3, length = 5

方法1(蛮力)

查找总和小于或等于k的所有子数组, 并返回最大长度的子数组。

时间复杂度：O(n ^ 2)

方法2(高效)：

一种有效的方法是使用滑动窗口技术。

遍历数组, 并检查在添加当前元素时其总和是否小于或等于k。

如果小于k, 则将其相加并增加计数。

Else

删除子数组的第一个元素并减少计数。

再次检查在添加当前元素时, 其总和是否小于或等于k。

如果小于k, 则将其相加并增加计数。

跟踪最大计数。

C ++

//A C++ program to find longest subarray with
//sum of elements at-least k.
#include <bits/stdc++.h>
using namespace std;
  
//function to find the length of largest subarray
//having sum atmost k.
int atMostSum( int arr[], int n, int k)
{
     int sum = 0;
     int cnt = 0, maxcnt = 0;
  
     for ( int i = 0; i <n; i++) {
          
         //If adding current element doesn't
         //cross limit add it to current window
         if ((sum + arr[i]) <= k) {
             sum += arr[i]; 
             cnt++;
         } 
  
         //Else, remove first element of current
         //window and add the current element
         else if (sum!=0)
         {
             sum = sum - arr[i - cnt] + arr[i];
         }
  
         //keep track of max length.
         maxcnt = max(cnt, maxcnt); 
     }
     return maxcnt;
}
  
//Driver function
int main()
{
     int arr[] = {1, 2, 1, 0, 1, 1, 0};
     int n = sizeof (arr) /sizeof (arr[0]);
     int k = 4;
  
     cout <<atMostSum(arr, n, k);
     return 0;
}

Java

//Java program to find longest subarray with
//sum of elements at-least k.
import java.util.*;
  
class GFG {
      
     //function to find the length of largest
     //subarray having sum atmost k.
     public static int atMostSum( int arr[], int n, int k)
     {
         int sum = 0 ;
         int cnt = 0 , maxcnt = 0 ;
      
         for ( int i = 0 ; i <n; i++) {
              
             //If adding current element doesn't
             //cross limit add it to current window
             if ((sum + arr[i]) <= k) {
                 sum += arr[i]; 
                 cnt++;
             } 
      
             //Else, remove first element of current
             //window.
             else if (sum!= 0 )
            {
             sum = sum - arr[i - cnt] + arr[i];
            }
      
             //keep track of max length.
             maxcnt = Math.max(cnt, maxcnt); 
         }
         return maxcnt;
     }
      
     /* Driver program to test above function */
     public static void main(String[] args) 
     {
         int arr[] = { 1 , 2 , 1 , 0 , 1 , 1 , 0 };
         int n = arr.length;
         int k = 4 ;
      
         System.out.print(atMostSum(arr, n, k));
              
     }
}
//This code is contributed by Arnav Kr. Mandal.

Python3

# Python3 program to find longest subarray
# with sum of elements at-least k.
  
# function to find the length of largest 
# subarray having sum atmost k.
def atMostSum(arr, n, k):
     _sum = 0
     cnt = 0
     maxcnt = 0
      
     for i in range (n):
  
         # If adding current element doesn't
         # Cross limit add it to current window
         if ((_sum + arr[i]) <= k):
             _sum + = arr[i]
             cnt + = 1
          
         # Else, remove first element of current
         # window and add the current element
         elif ( sum ! = 0 ):
             _sum = _sum - arr[i - cnt] + arr[i]
          
         # keep track of max length.
         maxcnt = max (cnt, maxcnt)
  
     return maxcnt
      
# Driver function
arr = [ 1 , 2 , 1 , 0 , 1 , 1 , 0 ]
n = len (arr)
k = 4
print (atMostSum(arr, n, k))
  
# This code is contributed by "Abhishek Sharma 44"

C#

//C# program to find longest subarray 
//with sum of elements at-least k.
using System;
  
class GFG {
      
     //function to find the length of largest
     //subarray having sum atmost k.
     public static int atMostSum( int []arr, int n, int k)
     {
         int sum = 0;
         int cnt = 0, maxcnt = 0;
      
         for ( int i = 0; i <n; i++) {
              
             //If adding current element doesn't
             //cross limit add it to current window
             if ((sum + arr[i]) <= k) {
                 sum += arr[i]; 
                 cnt++;
             } 
      
             //Else, remove first element 
             //of current window.
             else if (sum!=0)
             {
                 sum = sum - arr[i - cnt] + arr[i];
             }
      
             //keep track of max length.
             maxcnt = Math.Max(cnt, maxcnt); 
         }
         return maxcnt;
     }
      
     //Driver Code
     public static void Main() 
     {
         int []arr = {1, 2, 1, 0, 1, 1, 0};
         int n = arr.Length;
         int k = 4;
      
         Console.Write(atMostSum(arr, n, k));
              
     }
}
  
//This code is contributed by Nitin Mittal

的PHP

<?php 
//A PHP program to find longest 
//subarray with sum of elements 
//at-least k.
  
//function to find the length 
//of largest subarray having 
//sum atmost k.
function atMostSum(& $arr , $n , $k )
{
     $sum = 0;
     $cnt = 0;
     $maxcnt = 0;
  
     for ( $i = 0; $i <$n ; $i ++)
     { 
         //If adding current element 
         //doesn't cross limit add 
         //it to current window
         if (( $sum + $arr [ $i ]) <= $k )
         {
             $sum += $arr [ $i ] ;
             $cnt += 1 ;
         }
  
         //Else, remove first element 
         //of current window and add 
         //the current element
         else if ( $sum != 0)
             $sum = $sum - $arr [ $i - $cnt ] + 
                                $arr [ $i ];
          
         //keep track of max length.
         $maxcnt = max( $cnt , $maxcnt );
     }
     return $maxcnt ;
}
  
//Driver Code
$arr = array (1, 2, 1, 0, 1, 1, 0);
$n = sizeof( $arr );
$k = 4;
  
print (atMostSum( $arr , $n , $k ));
  
//This code is contributed
//by ChitraNayal
?>

输出如下：

5

时间复杂度： O(n)

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。