Find Subarrays With Equal Sum - Solution & Explanation
Problem Statement
Given a 0-indexed integer array nums, determine whether there exist two subarrays of length 2 with equal sum. Note that the two subarrays must begin at different indices.
Return true if these subarrays exist, and false otherwise.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [4,2,4] Output: true Explanation: The subarrays with elements [4,2] and [2,4] have the same sum of 6.
Example 2:
Input: nums = [1,2,3,4,5] Output: false Explanation: No two subarrays of size 2 have the same sum.
Example 3:
Input: nums = [0,0,0] Output: true Explanation: The subarrays [nums[0],nums[1]] and [nums[1],nums[2]] have the same sum of 0. Note that even though the subarrays have the same content, the two subarrays are considered different because they are in different positions in the original array.
Constraints:
2 <= nums.length <= 1000-109 <= nums[i] <= 109
Approach Overview
Problem Overview: You are given an integer array and must determine whether two different subarrays of length 2 have the same sum. In other words, check if there exist indices i and j such that nums[i] + nums[i+1] == nums[j] + nums[j+1] with i != j. The task reduces to computing sums of adjacent pairs and detecting duplicates.
Approach 1: Brute Force Comparison (Time: O(n²), Space: O(1))
The straightforward method compares every pair of length-2 subarrays. First iterate through the array and compute the sum for each adjacent pair. For every pair starting at index i, run another loop for indices j > i and check whether nums[i] + nums[i+1] equals nums[j] + nums[j+1]. If a match appears, return true. This approach works because it exhaustively checks all possible pair combinations, but the nested loops make the runtime quadratic. With arrays up to large sizes, O(n²) quickly becomes inefficient. It uses constant extra memory since only a few variables are stored during comparisons.
Approach 2: HashSet for Pair Sums (Time: O(n), Space: O(n))
A more efficient solution stores each adjacent-pair sum in a HashSet. Iterate once through the array and compute pairSum = nums[i] + nums[i+1]. Before inserting the value, check if the set already contains that sum. If it does, two subarrays share the same total and the answer is immediately true. Otherwise, insert the sum and continue scanning. This works because a hash set provides average O(1) lookup and insertion, turning duplicate detection into a linear-time process.
The key insight is that the problem does not require storing indices or the actual subarrays. Only the pair sums matter. As soon as a duplicate sum appears, two different adjacent pairs must produce it. This pattern—tracking seen values to detect duplicates—is common in hash table problems and appears frequently in array scanning tasks.
Recommended for interviews: The HashSet approach is what interviewers expect. The brute force method demonstrates you understand the problem constraints and baseline logic, but the optimized solution shows you recognize duplicate detection patterns and can apply a hash-based lookup to reduce the time complexity from O(n²) to O(n).
Approach 1: Brute Force Approach
This approach involves iterating through each possible pair of consecutive elements to calculate their sums and comparing these sums to find duplicates. Though simple, it may not be the most efficient for large arrays.
The C implementation uses nested loops to check every pair of adjacent elements, calculating their sums and comparing them for equality. If a matching sum is found, it returns true. Otherwise, it returns false after all checks.
Complexity
The time complexity is O(n^2) due to the nested loops, and the space complexity is O(1) since no additional data structures are used.
Approach 2: Optimized HashSet Approach
The optimized approach utilizes a hash set for storing subarray sums, providing faster lookups. By iterating once over the array, and storing each consecutive subarray sum, collisions in the hash set indicate duplicate sums, hence satisfying our condition.
This C solution introduces a hash set to the loop handling logic. By storing and checking sums in a structured manner, efficiency gains are achieved through reduced duplication checks.
Complexity
The improved time complexity operates at O(n) due to constant time complexity operations with hash functions, while space complexity scales with O(n) for hash set storage.
Approach 3: Hash Table
We can traverse the array nums, and use a hash table vis to record the sum of every two adjacent elements in the array. If the sum of the current two elements has already appeared in the hash table, then return true. Otherwise, add the sum of the current two elements to the hash table.
If we finish traversing and haven't found two subarrays that meet the condition, return false.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | The time complexity is O(n^2) due to the nested loops, and the space complexity is O(1) since no additional data structures are used. |
| Optimized HashSet Approach | The improved time complexity operates at O(n) due to constant time complexity operations with hash functions, while space complexity scales with O(n) for hash set storage. |
| Hash Table | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Comparison | O(n²) | O(1) | Good for understanding the problem or when the array size is very small |
| HashSet Duplicate Pair Sum | O(n) | O(n) | Best general solution for detecting repeated adjacent pair sums efficiently |
Video Solution
Leetcode 2395. Find Subarrays With Equal Sum | Biweekly Contest 86. • Code with Alisha • 2,390 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find Subarrays With Equal Sum easy or hard?
Find Subarrays With Equal Sum Python/Java solution
How to solve Find Subarrays With Equal Sum in O(n)?
What is the best approach for Find Subarrays With Equal Sum?
Is Find Subarrays With Equal Sum asked at Google/Amazon/Meta?
What data structure is used in Find Subarrays With Equal Sum?
What is the time complexity of Find Subarrays With Equal Sum?
Ready to solve this problem?
Practice Find Subarrays With Equal Sum with our built-in code editor and test cases.
Practice on FleetCode