LeetCode 560 - Subarray Sum Equals K

Link: https://leetcode.com/problems/subarray-sum-equals-k/description/

import java.util.*;

/**
 * LeetCode 560: Subarray Sum Equals K
 * 
 * Problem: Given an array of integers (positive and negative) and a target sum k,
 * find the total number of continuous subarrays that sum to exactly k.
 * 
 * Key Implementation Details:
 * 1. Handles both positive and negative numbers
 * 2. Efficient space-time trade-off using HashMap
 * 3. Input validation and edge cases
 * 4. Proper handling of zero sum edge cases
 * 
 * Example:
 * Input: nums = [1,1,1], k = 2
 * Output: 2
 * Explanation: [1,1] appears twice
 */
public class SubarraySum {

    /**
     * Finds number of continuous subarrays summing to k using prefix sum and HashMap.
     * 
     * Time Complexity: O(n) - single pass through array
     * Space Complexity: O(n) - for storing prefix sums
     * 
     * @param nums Input array of integers
     * @param k Target sum
     * @return Number of continuous subarrays summing to k
     */
    public Result subarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return new Result(0, new ArrayList<>());
        }

        // Map to store prefix sum frequencies
        Map<Integer, List<Integer>> sumMap = new HashMap<>();
        sumMap.put(0, new ArrayList<>(Arrays.asList(-1)));  // Handle subarrays starting from index 0

        int currentSum = 0;
        int count = 0;
        List<int[]> subarrays = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            currentSum += nums[i];

            // If (currentSum - k) exists in map, we found subarrays summing to k
            if (sumMap.containsKey(currentSum - k)) {
                List<Integer> startIndices = sumMap.get(currentSum - k);
                count += startIndices.size();

                // Store all subarrays found
                for (int startIndex : startIndices) {
                    subarrays.add(new int[]{startIndex + 1, i});
                }
            }

            // Add current sum to map
            sumMap.computeIfAbsent(currentSum, x -> new ArrayList<>()).add(i);
        }

        return new Result(count, subarrays);
    }

    /**
     * Class to hold result information including all found subarrays
     */
    public static class Result {
        public final int count;
        public final List<int[]> subarrays;

        public Result(int count, List<int[]> subarrays) {
            this.count = count;
            this.subarrays = subarrays;
        }
    }

    public static void main(String[] args) {
        SubarraySum solution = new SubarraySum();

        // Test cases
        TestCase[] testCases = {
            new TestCase(
                new int[]{1, 1, 1},
                2,
                "Basic case with multiple solutions"
            ),
            new TestCase(
                new int[]{1, 2, 3, -3, 1, 1, 1, 4, 2, -3},
                3,
                "Complex case with negative numbers"
            ),
            new TestCase(
                new int[]{1},
                1,
                "Single element equals target"
            ),
            new TestCase(
                new int[]{1, -1, 1, -1},
                0,
                "Zero sum with alternating numbers"
            ),
            new TestCase(
                new int[]{-2, -1, 2, 1},
                1,
                "Mixed positive and negative"
            ),
            new TestCase(
                new int[]{1, 2, 3, 4, 5},
                9,
                "Multiple consecutive elements"
            ),
            new TestCase(
                new int[]{0, 0, 0, 0},
                0,
                "Multiple zeros with zero target"
            ),
            new TestCase(
                new int[]{4, 2, -3, 1, 6},
                0,
                "No subarrays summing to target"
            ),
            new TestCase(
                new int[]{-1, -1, 1},
                0,
                "Negative numbers with zero target"
            ),
            new TestCase(
                new int[]{100, -100, 100, -100, 100, -100},
                100,
                "Large alternating numbers"
            )
        };

        for (TestCase test : testCases) {
            runTest(solution, test);
        }
    }

    private static class TestCase {
        int[] nums;
        int k;
        String description;

        TestCase(int[] nums, int k, String description) {
            this.nums = nums;
            this.k = k;
            this.description = description;
        }
    }

    private static void runTest(SubarraySum solution, TestCase test) {
        System.out.println("\nTest: " + test.description);
        System.out.println("Input array: " + Arrays.toString(test.nums));
        System.out.println("Target sum: " + test.k);

        Result result = solution.subarraySum(test.nums, test.k);
        System.out.println("Number of subarrays found: " + result.count);

        if (result.count > 0) {
            System.out.println("Subarrays found:");
            for (int[] subarray : result.subarrays) {
                int[] sequence = Arrays.copyOfRange(test.nums, subarray[0], subarray[1] + 1);
                System.out.println("  Indices [" + subarray[0] + ", " + subarray[1] + "]: " + 
                                 Arrays.toString(sequence) + " = " + Arrays.stream(sequence).sum());
            }

            // Verify all subarrays sum to target
            boolean allValid = true;
            for (int[] subarray : result.subarrays) {
                int sum = 0;
                for (int i = subarray[0]; i <= subarray[1]; i++) {
                    sum += test.nums[i];
                }
                if (sum != test.k) {
                    allValid = false;
                    break;
                }
            }
            System.out.println("All subarrays verified: " + allValid);
        }
    }
}