Coding Interview - Subarray Sum Equals K

Link : https://leetcode.com/discuss/post/124820/facebook-subarray-sum-equals-k-by-baopha-n3y2/

Pattern: Sliding Window

import java.util.*;

/**
 * Continuous Sequence Sum Problem
 * 
 * Problem: Given a sequence of positive integers and a target sum k,
 * find if there exists a continuous sequence that sums to exactly k.
 * 
 * Approaches implemented:
 * 1. Sliding Window - O(n)
 * 2. Brute Force - O(n²) [for comparison]
 * 
 * Key Implementation Details:
 * - Input validation
 * - Proper handling of edge cases
 * - Space-efficient solution
 */
public class ContinuousSequenceSum {

    /**
     * Finds continuous sequence summing to k using sliding window.
     * 
     * Time Complexity: O(n) - single pass through array
     * Space Complexity: O(1) - only uses a few variables
     * 
     * @param nums Input array of positive integers
     * @param k Target sum
     * @return Result containing existence of sequence and the sequence if found
     */
    public Result findSequenceWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new Result(false, new int[0], new int[0]);
        }

        int start = 0;
        int currentSum = 0;

        // Slide window through array
        for (int end = 0; end < nums.length; end++) {
            currentSum += nums[end];

            // Shrink window while sum is too large
            while (currentSum > k && start <= end) {
                currentSum -= nums[start];
                start++;
            }

            // Check if we found target sum
            if (currentSum == k) {
                int[] sequence = Arrays.copyOfRange(nums, start, end + 1);
                int[] indices = new int[]{start, end};
                return new Result(true, sequence, indices);
            }
        }

        return new Result(false, new int[0], new int[0]);
    }

    /**
     * Finds continuous sequence summing to k using brute force.
     * Included for comparison and to demonstrate the benefits of sliding window.
     * 
     * Time Complexity: O(n²) - nested loops
     * Space Complexity: O(1) - only uses a few variables
     * 
     * @param nums Input array of positive integers
     * @param k Target sum
     * @return Result containing existence of sequence and the sequence if found
     */
    public Result findSequenceBrute(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new Result(false, new int[0], new int[0]);
        }

        // Try all possible sequences
        for (int start = 0; start < nums.length; start++) {
            int sum = 0;
            for (int end = start; end < nums.length; end++) {
                sum += nums[end];
                if (sum == k) {
                    int[] sequence = Arrays.copyOfRange(nums, start, end + 1);
                    int[] indices = new int[]{start, end};
                    return new Result(true, sequence, indices);
                }
                if (sum > k) {
                    break;  // Early exit since all numbers are positive
                }
            }
        }

        return new Result(false, new int[0], new int[0]);
    }

    /**
     * Class to hold result information including the sequence if found
     */
    public static class Result {
        public final boolean exists;
        public final int[] sequence;
        public final int[] indices;

        public Result(boolean exists, int[] sequence, int[] indices) {
            this.exists = exists;
            this.sequence = sequence;
            this.indices = indices;
        }
    }

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

        // Test cases
        TestCase[] testCases = {
            new TestCase(
                new int[]{23, 5, 4, 7, 2, 11},
                20,
                "Standard case (7 + 2 + 11 = 20)"
            ),
            new TestCase(
                new int[]{1, 3, 5, 23, 2},
                8,
                "Adjacent elements (3 + 5 = 8)"
            ),
            new TestCase(
                new int[]{1, 3, 5, 23, 2},
                7,
                "No sequence exists"
            ),
            new TestCase(
                new int[]{1},
                1,
                "Single element equals target"
            ),
            new TestCase(
                new int[]{5},
                6,
                "Single element doesn't equal target"
            ),
            new TestCase(
                new int[]{1, 2, 3, 4, 5},
                15,
                "Entire array sums to target"
            ),
            new TestCase(
                new int[]{1, 1, 1, 1, 1},
                3,
                "Sequence of same numbers"
            ),
            new TestCase(
                new int[]{10, 20, 30, 40, 50},
                30,
                "Single large element"
            ),
            new TestCase(
                new int[]{2, 4, 6, 8, 10},
                11,
                "No sequence possible"
            ),
            new TestCase(
                new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
                15,
                "Multiple possible sequences (returns first)"
            )
        };

        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(ContinuousSequenceSum 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);

        // Test sliding window approach
        Result windowResult = solution.findSequenceWindow(test.nums, test.k);
        System.out.println("\nSliding Window approach:");
        printResult(windowResult);

        // Test brute force approach
        Result bruteResult = solution.findSequenceBrute(test.nums, test.k);
        System.out.println("\nBrute Force approach:");
        printResult(bruteResult);

        // Verify both approaches give same result
        boolean match = windowResult.exists == bruteResult.exists &&
                       Arrays.equals(windowResult.sequence, bruteResult.sequence);
        System.out.println("\nBoth approaches match: " + match);

        // Verify sequence sum if exists
        if (windowResult.exists) {
            int sum = Arrays.stream(windowResult.sequence).sum();
            System.out.println("Sequence sum verification: " + 
                             (sum == test.k ? "PASSED" : "FAILED") +
                             " (sum = " + sum + ")");
        }
    }

    private static void printResult(Result result) {
        if (result.exists) {
            System.out.println("Found sequence: " + Arrays.toString(result.sequence));
            System.out.println("At indices: [" + result.indices[0] + ", " + result.indices[1] + "]");
            System.out.println("Sum: " + Arrays.stream(result.sequence).sum());
        } else {
            System.out.println("No sequence found");
        }
    }
}