Find Subarrays With Equal Sum

Difficulty: Easy | Acceptance: 67.00% | Paid: No Topics: Array, Hash Table

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.

• Examples
• Constraints
• Brute Force
• Hash Set

Examples

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.

Constraints

2 <= nums.length <= 1000
-10⁹ <= nums[i] <= 10⁹

Brute Force

Intuition Compare every pair of subarrays of length 2 to check if any two have the same sum.

Steps

• Iterate through all possible starting indices for the first subarray.
• For each first subarray, iterate through all possible starting indices for the second subarray.
• Compare the sums and return true if they match.
• Return false if no matching pairs found.

from typing import List

class Solution:
    def findSubarrays(self, nums: List[int]) -> bool:
        n = len(nums)
        for i in range(n - 1):
            sum1 = nums[i] + nums[i + 1]
            for j in range(i + 1, n - 1):
                sum2 = nums[j] + nums[j + 1]
                if sum1 == sum2:
                    return True
        return False

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: Simple but inefficient for large arrays.

Hash Set

Intuition Store all subarray sums in a hash set. If we encounter a sum that already exists, we found two subarrays with equal sum.

Steps

• Create an empty hash set to store subarray sums.
• Iterate through the array, calculating the sum of each subarray of length 2.
• If a sum is already in the set, return true.
• Otherwise, add the sum to the set.
• Return false if no duplicate sums found.

from typing import List

class Solution:
    def findSubarrays(self, nums: List[int]) -> bool:
        seen = set()
        for i in range(len(nums) - 1):
            subarray_sum = nums[i] + nums[i + 1]
            if subarray_sum in seen:
                return True
            seen.add(subarray_sum)
        return False

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Optimal solution with linear time complexity.