# Find Subarrays With Equal Sum
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-subarrays-with-equal-sum)
Canonical: https://scaleengineer.com/dsa/problems/find-subarrays-with-equal-sum
**Data structures:** Array, Hash Table
**Companies:** [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley)
---
## Problem
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
## Brute Force (Nested Loops)
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.
**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.
**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.
### Explanation
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.
```java
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
    }
}
```
### Algorithm
*   Get the length of the array, `n`. If `n < 3`, return `false` as it's impossible to form two distinct subarrays of length 2.
*   Start an outer loop with index `i` from `0` to `n - 2`.
*   Inside the outer loop, calculate the sum of the subarray `[nums[i], nums[i+1]]`. Store it in `sum1`.
*   Start an inner loop with index `j` from `i + 1` to `n - 2`.
*   Inside the inner loop, calculate the sum of the subarray `[nums[j], nums[j+1]]`. Store it in `sum2`.
*   Compare `sum1` and `sum2`. If they are equal, return `true`.
*   If the loops finish without returning, it means no equal-sum subarrays were found. Return `false`.

## Optimized Approach using a Hash Set
A more efficient approach is to use a hash set to keep track of the sums of subarrays encountered so far. This allows us to check for a duplicate sum in constant time on average, reducing the overall time complexity from quadratic to linear.
**Time:** O(N), where N is the length of the `nums` array. We iterate through the array once (N-1 times). Each operation on the hash set (add and check for existence) takes O(1) time on average. · **Space:** O(N). In the worst-case scenario, all N-1 subarray sums are distinct, and we would store all of them in the hash set. Thus, the space required is proportional to the size of the input array.
**Pros:** Highly efficient with a linear time complexity, making it suitable for large inputs.; The logic is still relatively simple to follow.
**Cons:** Requires extra memory to store the hash set, which can be up to O(N) in space.
### Explanation
The core idea is to iterate through the array and calculate the sum of each possible subarray of length 2. As we calculate each sum, we check if this sum already exists in a hash set.
- If the sum is already in the set, it means we have previously encountered a different subarray (starting at an earlier index) with the same sum. We can then immediately return `true`.
- If the sum is not in the set, we add it to the set and continue to the next subarray.
If we iterate through all possible subarrays without finding a duplicate sum, we can conclude that no such subarrays exist and return `false`. This avoids the need for a nested loop, making the solution much faster. We use a `HashSet<Long>` to handle potentially large sums and provide fast lookups.
```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean findSubarrays(int[] nums) {
        int n = nums.length;
        // A hash set to store the sums of subarrays of length 2.
        // We use Long to avoid potential integer overflow.
        Set<Long> seenSums = new HashSet<>();

        // Iterate through the array to form subarrays of length 2.
        // The loop goes up to n-2, which is the last possible starting index.
        for (int i = 0; i < n - 1; i++) {
            long currentSum = (long)nums[i] + nums[i+1];
            
            // Check if this sum has been seen before.
            // The add method of a Set returns false if the element is already present.
            if (!seenSums.add(currentSum)) {
                // If add returns false, it means the sum was already in the set.
                // We have found two subarrays with an equal sum.
                return true;
            }
        }
        
        // If the loop completes, no two subarrays have the same sum.
        return false;
    }
}
```
### Algorithm
*   Initialize an empty hash set, `seenSums`, to store sums of type `Long`.
*   Iterate through the input array `nums` with an index `i` from `0` to `n - 2`, where `n` is the length of the array.
*   For each `i`, calculate the sum of the subarray `[nums[i], nums[i+1]]`. Let's call it `currentSum`.
*   Attempt to add `currentSum` to the `seenSums` set.
*   If the `add` operation returns `false`, it means `currentSum` was already in the set. This indicates a duplicate sum has been found, so return `true`.
*   If the loop completes without finding any duplicates, return `false`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool findSubarrays(vector<int> &nums) {
    unordered_set<int> vis;
    for (int i = 1; i < nums.size(); ++i) {
      int x = nums[i - 1] + nums[i];
      if (vis.count(x)) {
        return true;
      }
      vis.insert(x);
    }
    return false;
  }
};

```

### Python

```python
class Solution:
    def findSubarrays(self, nums: List[int]) -> bool: vis = set() for a, b in pairwise(nums): if (x: = a + b) in vis: return True vis . add(x) return False

```