C# Coding Test Course, Sliding Window

Problem Description

Given an array as follows, let’s solve the problem of finding the length of the longest subarray whose sum does not exceed K.

            Input: nums = [1,2,3,4,5,6], K = 10
            Output: 4
            Explanation: [1,2,3,4] is the longest subarray whose sum does not exceed 10.
            

Problem Approach

By utilizing the sliding window technique, we traverse the array while maintaining the current sum, recording the maximum length when this sum does not exceed K. If the current sum exceeds K, we increment the starting index to reduce the sum and find a point that satisfies the condition.

Sliding Window Algorithm Implementation

            
            public class Solution {
                public int MaxLengthSubArray(int[] nums, int K) {
                    int left = 0, maxLength = 0, currentSum = 0;

                    for (int right = 0; right < nums.Length; right++) {
                        currentSum += nums[right];

                        while (currentSum > K) {
                            currentSum -= nums[left];
                            left++;
                        }

                        maxLength = Math.Max(maxLength, right - left + 1);
                    }

                    return maxLength;
                }
            }
            
            

Code Explanation

Now let’s look at each part of the code.

• Variable Initialization: Declare left, maxLength, and currentSum variables.
• For Loop: Use the right pointer right to traverse the array. Add the current number to currentSum.
• While Loop: If the current sum exceeds K, increment the left pointer left, subtracting the corresponding number from currentSum, and repeat this process until the sum is less than or equal to K.
• Update Maximum Length: Calculate the length of the current window and update maxLength.

Complexity Analysis

This algorithm traverses the array once, resulting in a time complexity of O(N). Additionally, it does not use extra space, giving it a space complexity of O(1). This demonstrates that the sliding window technique is very efficient.

Conclusion

The sliding window technique is a very useful skill in array and string problems, providing efficient solutions. This technique can be applied to various problems and will greatly aid your coding test preparation. As you practice solving problems, increase your understanding of the sliding window technique!