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

2021年3月12日13:48:07 发表评论 814 次浏览

本文概述

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

例子:

Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33
Output: Sum found between indexes 2 and 4

Input: arr[] = {10, 2, -2, -20, 10}, sum = -10
Output: Sum found between indexes 0 to 3

Input: arr[] = {-10, 0, 2, -2, -20, 10}, sum = 20
Output: 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 = - 10
  
subArraySum(arr, n, summ)
  
# This code is contributed by Mohit Kumar

C#

// 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

输出如下：

Sum found between indexes 1 and 2
木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: