算法题（最长子数组，元素总和不超过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 = 0for 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# 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 ?>

输出如下：