查找具有给定总和且在恒定空间中允许有负数的子数组 _数据结构

本文概述

建议：在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
C ++
Java
Python3
C#

给定一个未排序的整数数组, 找到一个添加到给定数字的子数组。如果存在多个子数组, 且总和为给定数, 则打印其中的任何一个。
例子:

Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33Output: Sum found between indexes 2 and 4Input: arr[] = {10, 2, -2, -20, 10}, sum = -10Output: Sum found between indexes 0 to 3Input: arr[] = {-10, 0, 2, -2, -20, 10}, sum = 20Output: No subarray with given sum exists.

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。【查找具有给定总和且在恒定空间中允许有负数的子数组】我们已经讨论了一种使用哈希在包含正负元素的数组中查找具有给定总和的子数组
在本文中, 讨论了一种不使用任何额外空间的方法。
这个想法是将数组修改为仅包含正元素：

在数组中找到最小的负元素, 然后将数组中的每个值增加找到的最小负元素的绝对值。

我们可能会注意到, 在进行了上述修改之后, 每个子数组的总和也将增加：

(number of elements in the subarray) * (absolute value of min element)

在输入数组中进行上述修改之后, 任务减少为在给定的仅包含正数的数组中查找具有新目标和的子数组。这可以在O(N)时间和恒定空间中使用滑动窗口技术来完成。
每次在窗口中添加元素时, 将目标和增加最小元素的绝对值, 类似地, 在从当前窗口中删除元素时, 将目标和减少最小元素的绝对值, 以便对于每个长度为的子数组假设为K, 则更新后的目标总和将为：

targetSum = sum + K*abs(minimum element)

下面是相同的方法：

初始化变量curr_sum作为第一个元素。
变量curr_sum指示当前子数组的总和。
从第二个元素开始, 然后将所有元素一一添加到curr_sum, 并保持目标总和增加abs(最小元素)。
如果curr_sum等于目标总和, 则打印解决方案。
如果curr_sum超过总和, 则在curr_sum大于总和时删除尾随元素, 并将目标总和递减abs(最小元素)。

下面是上述方法的实现：
C ++

// C++ program to check if subarray with sum // exists when negative elements are also present #include < bits/stdc++.h> using namespace std; // Function to check if subarray with sum // exists when negative elements are also present void subArraySum( int arr[], int n, int sum) { int minEle = INT_MAX; // Find minimum element in the array for ( int i = 0; i < n; i++) minEle = min(arr[i], minEle); // Initialize curr_sum as value of first element // and starting point as 0 int curr_sum = arr[0] + abs (minEle), start = 0, i; // Starting window length will be 1, // For generating new target sum, // add abs(minEle) to sum only 1 time int targetSum = sum; // Add elements one by one to curr_sum // and if the curr_sum exceeds the // updated sum, then remove starting element for (i = 1; i < = n; i++) {// If curr_sum exceeds the sum, // then remove the starting elements while (curr_sum - (i - start) * abs (minEle) > targetSum & & start < i - 1) { curr_sum = curr_sum - arr[start] - abs (minEle); start++; }// If curr_sum becomes equal to sum, then return true if (curr_sum - (i - start) * abs (minEle) == targetSum) { cout < < "Sum found between indexes " < < start < < " and " < < i - 1; return ; }// Add this element to curr_sum if (i < n) { curr_sum = curr_sum + arr[i] + abs (minEle); } }// If we reach here, then no subarray cout < < "No subarray found" ; }// Driver Code int main() { int arr[] = { 10, -12, 2, -2, -20, 10 }; int n = sizeof (arr) / sizeof (arr[0]); int sum = -10; subArraySum(arr, n, sum); return 0; }

Java

// Java program to check if subarray with sum // exists when negative elements are also present class GFG {// Function to check if subarray with sum // exists when negative elements are also present static void subArraySum( int arr[], int n, int sum) { int minEle = Integer.MAX_VALUE; // Find minimum element in the array for ( int i = 0 ; i < n; i++) minEle = Math.min(arr[i], minEle); // Initialize curr_sum as value of // first element and starting point as 0 int curr_sum = arr[ 0 ] + Math.abs(minEle); int start = 0 , i; // Starting window length will be 1, // For generating new target sum, // add abs(minEle) to sum only 1 time int targetSum = sum; // Add elements one by one to curr_sum // and if the curr_sum exceeds the // updated sum, then remove starting element for (i = 1 ; i < = n; i++) { // If curr_sum exceeds the sum, // then remove the starting elements while (curr_sum - (i - start) * Math.abs(minEle) > targetSum & & start < i - 1 ) { curr_sum = curr_sum - arr[start] - Math.abs(minEle); start++; } // If curr_sum becomes equal to sum, // then return true if (curr_sum - (i - start) * Math.abs(minEle) == targetSum) { System.out.println( "Sum found between indexes " + start + " and " + (i - 1 )); return ; } // Add this element to curr_sum if (i < n) { curr_sum = curr_sum + arr[i] + Math.abs(minEle); } } // If we reach here, then no subarray System.out.println( "No subarray found" ); } // Driver Code public static void main (String[] args) { int arr[] = { 10 , - 12 , 2 , - 2 , - 20 , 10 }; int n = arr.length; int sum = - 10 ; subArraySum(arr, n, sum); } }// This code is contributed by AnkitRai01

Python3

# Python3 program to check if subarray with summ # exists when negative elements are also present# Function to check if subarray with summ # exists when negative elements are also present def subArraySum(arr, n, summ): minEle = 10 * * 9# Find minimum element in the array for i in range (n): minEle = min (arr[i], minEle)# Initialize curr_summ as value of # first element and starting poas 0 curr_summ = arr[ 0 ] + abs (minEle) start = 0# Starting window length will be 1, # For generating new target summ, # add abs(minEle) to summ only 1 time targetSum = summ# Add elements one by one to curr_summ # and if the curr_summ exceeds the # updated summ, then remove starting element for i in range ( 1 , n + 1 ):# If curr_summ exceeds the summ, # then remove the starting elements while (curr_summ - (i - start) * abs (minEle) > targetSum and start < i - 1 ): curr_summ = curr_summ - arr[start] - abs (minEle) start + = 1# If curr_summ becomes equal to summ, # then return true if (curr_summ - (i - start) * abs (minEle) = = targetSum): print ( "Sum found between indexes" , start, "and" , i - 1 ) return# Add this element to curr_summ if (i < n): curr_summ = curr_summ + arr[i] + abs (minEle)# If we reach here, then no subarray print ( "No subarray found" )# Driver Code arr = [ 10 , - 12 , 2 , - 2 , - 20 , 10 ] n = len (arr)summ = - 10subArraySum(arr, n, summ)# This code is contributed by Mohit Kumar

// C# program to check if subarray // with sum exists when negative // elements are also present using System; class GFG {// Function to check if subarray // with sum exists when negative // elements are also present static void subArraySum( int []arr, int n, int sum) { int minEle = int .MaxValue; int i; // Find minimum element in the array for (i = 0; i < n; i++) minEle = Math.Min(arr[i], minEle); // Initialize curr_sum as value of // first element and starting point as 0 int curr_sum = arr[0] + Math.Abs(minEle); int start = 0; // Starting window length will be 1, // For generating new target sum, // add abs(minEle) to sum only 1 time int targetSum = sum; // Add elements one by one to curr_sum // and if the curr_sum exceeds the // updated sum, then remove starting element for (i = 1; i < = n; i++) { // If curr_sum exceeds the sum, // then remove the starting elements while (curr_sum - (i - start) * Math.Abs(minEle) > targetSum & & start < i - 1) { curr_sum = curr_sum - arr[start] - Math.Abs(minEle); start++; } // If curr_sum becomes equal to sum, // then return true if (curr_sum - (i - start) * Math.Abs(minEle) == targetSum) { Console.Write( "Sum found between indexes " + start + " and " + (i - 1)); return ; } // Add this element to curr_sum if (i < n) { curr_sum = curr_sum + arr[i] + Math.Abs(minEle); } } // If we reach here, then no subarray Console.Write( "No subarray found" ); } // Driver Code static public void Main () { int []arr = { 10, -12, 2, -2, -20, 10 }; int n = arr.Length; int sum = -10; subArraySum(arr, n, sum); } }// This code is contributed by ajit

输出如下：