Find Subarrays With Equal Sum
EasyPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly translates the problem statement into code. It iterates through all possible starting positions for the first subarray and, for each, iterates through all subsequent possible starting positions for the second subarray. It then compares their sums.
Algorithm
- Get the length of the array,
n. Ifn < 3, returnfalseas it's impossible to form two distinct subarrays of length 2. - Start an outer loop with index
ifrom0ton - 2. - Inside the outer loop, calculate the sum of the subarray
[nums[i], nums[i+1]]. Store it insum1. - Start an inner loop with index
jfromi + 1ton - 2. - Inside the inner loop, calculate the sum of the subarray
[nums[j], nums[j+1]]. Store it insum2. - Compare
sum1andsum2. If they are equal, returntrue. - If the loops finish without returning, it means no equal-sum subarrays were found. Return
false.
Walkthrough
The algorithm uses two nested loops to form all possible pairs of distinct subarrays of length 2. The outer loop, with index i, selects the first subarray [nums[i], nums[i+1]]. The inner loop, with index j, selects the second subarray [nums[j], nums[j+1]], where j is always greater than i to ensure the subarrays start at different indices and to avoid redundant comparisons. For each pair, we calculate their sums. If the sums are equal, we've found a match and can immediately return true. If the loops complete without finding any match, it means no such pair exists, and we return false. Since the sum of two numbers can exceed the standard integer limit, we use a long to store the sum to prevent overflow.
class Solution { public boolean findSubarrays(int[] nums) { int n = nums.length; // We need at least two subarrays of length 2, so the array must have at least 3 elements. // e.g., [a, b, c] -> [a,b] and [b,c]. // If n < 3, we can't form two distinct subarrays of length 2. if (n < 3) { return false; } // Outer loop for the first subarray for (int i = 0; i < n - 1; i++) { // Using long to prevent integer overflow long sum1 = (long)nums[i] + nums[i+1]; // Inner loop for the second subarray, starting from i + 1 for (int j = i + 1; j < n - 1; j++) { long sum2 = (long)nums[j] + nums[j+1]; if (sum1 == sum2) { return true; // Found two subarrays with equal sum } } } return false; // No such subarrays found }}Complexity
Time
O(N^2), where N is the length of the `nums` array. The nested loops lead to a quadratic number of comparisons. The outer loop runs N-1 times, and the inner loop runs up to N-2 times.
Space
O(1). We only use a few variables to store loop indices and sums, so the memory usage is constant and does not depend on the input size.
Trade-offs
Pros
Very simple to conceptualize and implement.
Space-efficient as it uses constant extra space.
Cons
Inefficient for large arrays due to its quadratic time complexity.
Solutions
Solution
class Solution {public boolean findSubarrays(int[] nums) { Set<Integer> vis = new HashSet<>(); for (int i = 1; i < nums.length; ++i) { if (!vis.add(nums[i - 1] + nums[i])) { return true; } } return false; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.