Find Subarray with given sum in c#

Programming C#
1

To find a subarray with a given sum in C#, you can use a hash map (or dictionary) to keep track of cumulative sums as you iterate through the array. This allows you to efficiently check if a subarray with the required sum exists. Here’s a step-by-step explanation along with a code example.

Explanation

  1. Cumulative Sum: As you iterate through the array, calculate the cumulative sum of elements.

  2. Hash Map (Dictionary): Use a dictionary to store the cumulative sums and their corresponding indices. This will help you quickly check if the required sum exists.

  3. Checking for the Target Sum: For each cumulative sum, check if the difference between the current cumulative sum and the target sum exists in the dictionary. If it does, then a subarray with the desired sum exists.

Code Implementation

Here’s a sample implementation in C#:

using System;
using System.Collections.Generic;

class Program
{
    static void FindSubarrayWithSum(int[] arr, int targetSum)
    {
        // Dictionary to store cumulative sums and their indices
        Dictionary<int, int> sumMap = new Dictionary<int, int>();
        int cumulativeSum = 0;

        // Iterate through the array
        for (int i = 0; i < arr.Length; i++)
        {
            // Update the cumulative sum
            cumulativeSum += arr[i];

            // Check if the cumulative sum equals the target sum
            if (cumulativeSum == targetSum)
            {
                Console.WriteLine($"Subarray found from index 0 to {i}");
                return;
            }

            // Check if there is a cumulative sum that, when subtracted from the current sum, equals the target sum
            if (sumMap.ContainsKey(cumulativeSum - targetSum))
            {
                int startIndex = sumMap[cumulativeSum - targetSum] + 1;
                Console.WriteLine($"Subarray found from index {startIndex} to {i}");
                return;
            }

            // Store the cumulative sum in the dictionary
            sumMap[cumulativeSum] = i;
        }

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

    static void Main(string[] args)
    {
        int[] arr = { 1, 2, 3, 7, 5 };
        int targetSum = 12;
        FindSubarrayWithSum(arr, targetSum); // Output: Subarray found from index 2 to 4
    }
}

How the Code Works

  1. Initialize Variables: Create a dictionary sumMap to hold cumulative sums and their indices. Initialize cumulativeSum to zero.

  2. Iterate Through the Array:

    • For each element, update cumulativeSum.
    • Check for Target Sum: If cumulativeSum equals the target sum, print the starting index (0) and the current index (i).
    • Check for Subarray: If (cumulativeSum - targetSum) exists in the dictionary, it means there’s a subarray that sums to the target. Calculate the starting index from the stored index in the dictionary and print the result.

  3. Store Cumulative Sum: If the cumulative sum isn’t equal to the target or doesn’t lead to a valid subarray, store the cumulative sum and its index in the dictionary.

  4. Output: If no valid subarray is found after the loop, print a message indicating that.

Complexity

  • Time Complexity: O(n), where n is the number of elements in the array. We traverse the array once.
  • Space Complexity: O(n), for storing the cumulative sums in the dictionary.

This method efficiently finds a subarray with the given sum by leveraging cumulative sums and a hash map for quick lookups.