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

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

## 本文概述

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)

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