Language Selection
Choose your preferred programming language
Showing: Python
Subarray with Given Sum
Problem Statement
Given an array of positive integers nums and a positive integer target, return the indices of a contiguous subarray that sums to target. If there are multiple such subarrays, return any one of them.
Examples
Example 1:
Input: nums = [1,2,3,4,5], target = 9
Output: [1,3]
Explanation: The subarray [2,3,4] sums to 9.
Example 2:
Input: nums = [1,1,1], target = 2
Output: [0,1]
Explanation: The subarray [1,1] sums to 2.
Example 3:
Input: nums = [2,3,1,2,4,3], target = 7
Output: [2,4]
Explanation: The subarray [1,2,4] sums to 7.
Constraints
1 <= nums.length <= 10^51 <= nums[i] <= 10^41 <= target <= 10^9
Approach 1: Sliding Window (Optimal)
Algorithm
Use two pointers to maintain a sliding window and adjust based on current sum.
Steps:
- Initialize two pointers at start of array
- Expand window by moving right pointer
- If sum exceeds target, shrink window by moving left pointer
- Return indices when sum equals target
Implementation
Python:
def subarraySum(nums, target):
"""
Find subarray with given sum using sliding window
Time: O(n)
Space: O(1)
"""
left = 0
current_sum = 0
for right in range(len(nums)):
current_sum += nums[right]
# Shrink window if sum exceeds target
while current_sum > target and left <= right:
current_sum -= nums[left]
left += 1
# Check if we found the target sum
if current_sum == target:
return [left, right]
return [] # No subarray found
Java:
class Solution {
/**
* Find subarray with given sum using sliding window
* Time: O(n)
* Space: O(1)
*/
public int[] subarraySum(int[] nums, int target) {
int left = 0;
int currentSum = 0;
for (int right = 0; right < nums.length; right++) {
currentSum += nums[right];
// Shrink window if sum exceeds target
while (currentSum > target && left <= right) {
currentSum -= nums[left];
left++;
}
// Check if we found the target sum
if (currentSum == target) {
return new int[]{left, right};
}
}
return new int[]{}; // No subarray found
}
}
Go:
func subarraySum(nums []int, target int) []int {
/**
* Find subarray with given sum using sliding window
* Time: O(n)
* Space: O(1)
*/
left := 0
currentSum := 0
for right := 0; right < len(nums); right++ {
currentSum += nums[right]
// Shrink window if sum exceeds target
for currentSum > target && left <= right {
currentSum -= nums[left]
left++
}
// Check if we found the target sum
if currentSum == target {
return []int{left, right}
}
}
return []int{} // No subarray found
}
JavaScript:
/**
* Find subarray with given sum using sliding window
* Time: O(n)
* Space: O(1)
*/
function subarraySum(nums, target) {
let left = 0;
let currentSum = 0;
for (let right = 0; right < nums.length; right++) {
currentSum += nums[right];
// Shrink window if sum exceeds target
while (currentSum > target && left <= right) {
currentSum -= nums[left];
left++;
}
// Check if we found the target sum
if (currentSum === target) {
return [left, right];
}
}
return []; // No subarray found
}
C#:
public class Solution {
/// <summary>
/// Find subarray with given sum using sliding window
/// Time: O(n)
/// Space: O(1)
/// </summary>
public int[] SubarraySum(int[] nums, int target) {
int left = 0;
int currentSum = 0;
for (int right = 0; right < nums.Length; right++) {
currentSum += nums[right];
// Shrink window if sum exceeds target
while (currentSum > target && left <= right) {
currentSum -= nums[left];
left++;
}
// Check if we found the target sum
if (currentSum == target) {
return new int[] { left, right };
}
}
return new int[] {}; // No subarray found
}
}
Complexity Analysis
- Time Complexity: O(n) - Each element is visited at most twice
- Space Complexity: O(1) - Only constant extra space
Approach 2: Brute Force (Alternative)
Algorithm
Check all possible subarrays to find one with target sum.
Steps:
- For each starting index:
- For each ending index:
- Calculate sum of subarray
- Return indices if sum equals target
- For each ending index:
Implementation
Python:
def subarraySum_brute(nums, target):
"""
Find subarray with given sum using brute force
Time: O(n²)
Space: O(1)
"""
for i in range(len(nums)):
current_sum = 0
for j in range(i, len(nums)):
current_sum += nums[j]
if current_sum == target:
return [i, j]
return [] # No subarray found
Java:
class Solution {
/**
* Find subarray with given sum using brute force
* Time: O(n²)
* Space: O(1)
*/
public int[] subarraySumBrute(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
int currentSum = 0;
for (int j = i; j < nums.length; j++) {
currentSum += nums[j];
if (currentSum == target) {
return new int[]{i, j};
}
}
}
return new int[]{}; // No subarray found
}
}
Go:
func subarraySumBrute(nums []int, target int) []int {
/**
* Find subarray with given sum using brute force
* Time: O(n²)
* Space: O(1)
*/
for i := 0; i < len(nums); i++ {
currentSum := 0
for j := i; j < len(nums); j++ {
currentSum += nums[j]
if currentSum == target {
return []int{i, j}
}
}
}
return []int{} // No subarray found
}
JavaScript:
/**
* Find subarray with given sum using brute force
* Time: O(n²)
* Space: O(1)
*/
function subarraySumBrute(nums, target) {
for (let i = 0; i < nums.length; i++) {
let currentSum = 0;
for (let j = i; j < nums.length; j++) {
currentSum += nums[j];
if (currentSum === target) {
return [i, j];
}
}
}
return []; // No subarray found
}
C#:
public class Solution {
/// <summary>
/// Find subarray with given sum using brute force
/// Time: O(n²)
/// Space: O(1)
/// </summary>
public int[] SubarraySumBrute(int[] nums, int target) {
for (int i = 0; i < nums.Length; i++) {
int currentSum = 0;
for (int j = i; j < nums.Length; j++) {
currentSum += nums[j];
if (currentSum == target) {
return new int[] { i, j };
}
}
}
return new int[] {}; // No subarray found
}
}
Complexity Analysis
- Time Complexity: O(n²) - Check all possible subarrays
- Space Complexity: O(1) - Only constant extra space
Key Insights
- Sliding Window: Most efficient approach for positive integers
- Two Pointers: Use left and right pointers to maintain window
- Window Shrinking: Shrink window when sum exceeds target
- Positive Integers: Assumption allows sliding window approach
- Single Pass: Sliding window processes array only once
Edge Cases
- No Solution: Handle case where no subarray sums to target
- Single Element: Handle arrays with single element
- Target at Start: Handle target sum at beginning of array
- Target at End: Handle target sum at end of array
- Large Target: Handle target larger than array sum
Test Cases
def test_subarraySum():
# Test case 1: Normal case
nums1 = [1, 2, 3, 4, 5]
target1 = 9
result1 = subarraySum(nums1, target1)
expected1 = [1, 3]
assert result1 == expected1
# Test case 2: Multiple subarrays
nums2 = [1, 1, 1]
target2 = 2
result2 = subarraySum(nums2, target2)
expected2 = [0, 1]
assert result2 == expected2
# Test case 3: Single element
nums3 = [5]
target3 = 5
result3 = subarraySum(nums3, target3)
expected3 = [0, 0]
assert result3 == expected3
# Test case 4: No solution
nums4 = [1, 2, 3]
target4 = 7
result4 = subarraySum(nums4, target4)
expected4 = []
assert result4 == expected4
# Test both approaches
assert subarraySum(nums1, target1) == subarraySum_brute(nums1, target1)
print("All tests passed!")
test_subarraySum()
Follow-up Questions
- Subarray Sum Equals K: Handle negative numbers?
- Subarray Sum with Constraints: Add additional constraints?
- Subarray Sum with Modulo: Handle modulo operations?
- Subarray Sum in 2D: Handle 2D arrays?
- Subarray Sum with Weights: Handle weighted subarrays?
Common Mistakes
- Wrong Window Shrinking: Not shrinking window correctly
- Index Confusion: Confusing left and right pointers
- Edge Cases: Not handling no solution case
- Time Complexity: Not optimizing from O(n²) to O(n)
- Positive Assumption: Not considering negative numbers
Interview Tips
- Start with Brute Force: Show understanding of the problem
- Optimize with Sliding Window: Explain sliding window approach
- Handle Edge Cases: Mention no solution and single element cases
- Discuss Trade-offs: Compare time vs space complexity
- Follow-up Ready: Be prepared for negative numbers and other variations
Concept Explanations
Subarray with Given Sum: We need to find a contiguous subarray that sums to a target value and return its indices.
Sliding Window: We use two pointers to maintain a window of elements. We expand the window by moving the right pointer and shrink it by moving the left pointer when the sum exceeds the target.
Why Sliding Window Works: Since all numbers are positive, we can use the sliding window technique. When the sum exceeds the target, we know that adding more elements will only increase the sum, so we shrink the window.
Two Pointers: We use left and right pointers to maintain the current window. The left pointer represents the start of the subarray, and the right pointer represents the end.
Window Shrinking: When the current sum exceeds the target, we move the left pointer to the right, effectively removing elements from the left side of the window.
Efficient Processing: The sliding window approach processes each element at most twice (once when expanding, once when shrinking), giving us O(n) time complexity.
Space Optimization: We use O(1) extra space since we only maintain the current sum and two pointers.
Edge Case Handling: We need to handle cases where no subarray sums to the target, single element arrays, and arrays where the target is at the beginning or end.