Find a Continuous Subarray with a Given Sum in C#

Introduction

I'll demonstrate how to locate a continuous subarray in an integer array that precisely adds up to a specified amount in this blog. This is a common issue that comes up frequently in competitive programming and coding interviews. It's a fantastic method to practice effective searching strategies and get familiar with arrays.

I'll show you how to handle large arrays quickly and easily using the sliding window technique, which operates in linear time. I'll walk through the process, give a clear sample of C# code, and highlight significant edge cases to be aware of along the way.

Problem Statement

Determine the beginning and ending indices of a continuous subarray whose sum equals the goal sum, given an array of positive integers and the target sum. Returning any one of these subarrays is acceptable if there are several. Indicate it appropriately if there isn't a subarray of that kind.

Approach Explanation (Sliding Window)

Since the array only contains positive values, we can design a sliding window that tracks a running sum using two pointers, start and finish.

• At the start of the array, we initialize both pointers.
• Next, we add each element to our current sum while continuing to advance the end pointer.
• We shift the start pointer ahead to remove values and decrease the window if the total exceeds the target.
• We have located the desired subarray once the sum equals the desired value.
• By doing this, we can avoid checking every potential subarray, which speeds up the answer from O(n²) to O(n) time.

C# Code Implementation

using System;

class SubarrayWithGivenSum
{
    public static void FindSubarray(int[] arr, int targetSum)
    {
        int start = 0, currentSum = 0;

        for (int end = 0; end < arr.Length; end++)
        {
            currentSum += arr[end];

            // Shrink the window from the left if currentSum is greater than targetSum
            while (currentSum > targetSum && start < end)
            {
                currentSum -= arr[start];
                start++;
            }

            // Check if currentSum matches the targetSum
            if (currentSum == targetSum)
            {
                Console.WriteLine($"Subarray found from index {start} to {end}");
                return;
            }
        }

        Console.WriteLine("No subarray with the given sum found.");
    }

    static void Main(string[] args)
    {
        int[] arr = { 1, 2, 3, 7, 5 };
        int targetSum = 12;

        FindSubarray(arr, targetSum);
    }
}

Sample Output

Time & Space Complexity

• The temporal complexity is O(n) since we just traverse the array twice using our two pointers.
• Space is O(1) since we only use a few variables and don't need more storage.

Edge Cases to Keep in Mind

• What happens if there are negative integers in the array? You'll need to use an alternative strategy because the sliding window method won't function in such a situation.
• What happens if the goal sum appears in many subarrays? The first one this code discovers will be returned.
• What happens if the target is not reached by any subarray? To inform you, the code will produce a message stating that there isn't a subarray of that kind.