2395. Find Subarrays With Equal Sum - Solution

The 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
-10⁹ <= nums[i] <= 10⁹

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.

Python

def findSubarrays(nums):
    for i in range(len(nums) - 1):
        for j in range(i + 1, len(nums) - 1):
            if nums[i] + nums[i + 1] == nums[j] + nums[j + 1]:
                return True
    return False

nums = [4, 2, 4]
print(findSubarrays(nums))

Java

import java.util.Arrays;

public class SubarrayChecker {
    public static boolean findSubarrays(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                if (nums[i] + nums[i + 1] == nums[j] + nums[j + 1]) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums = {4, 2, 4};
        System.out.println(findSubarrays(nums));
    }
}

C++

#include <vector>
#include <iostream>
using namespace std;

bool findSubarrays(vector<int>& nums) {
    for (int i = 0; i < nums.size() - 1; i++) {
        for (int j = i + 1; j < nums.size() - 1; j++) {
            if (nums[i] + nums[i + 1] == nums[j] + nums[j + 1]) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    vector<int> nums = {4, 2, 4};
    cout << (findSubarrays(nums) ? "true" : "false") << endl;
    return 0;
}

JavaScript

function findSubarrays(nums) {
    for (let i = 0; i < nums.length - 1; i++) {
        for (let j = i + 1; j < nums.length - 1; j++) {
            if (nums[i] + nums[i + 1] === nums[j] + nums[j + 1]) {
                return true;
            }
        }
    }
    return false;
}

const nums = [4, 2, 4];
console.log(findSubarrays(nums));

#include <stdio.h>
#include <stdbool.h>

bool findSubarrays(int* nums, int numsSize) {
    for (int i = 0; i < numsSize - 1; i++) {
        for (int j = i + 1; j < numsSize - 1; j++) {
            if (nums[i] + nums[i + 1] == nums[j] + nums[j + 1]) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    int nums[] = {4, 2, 4};
    int size = sizeof(nums) / sizeof(nums[0]);
    printf("%s\n", findSubarrays(nums, size) ? "true" : "false");
    return 0;
}

using System;

public class SubarrayChecker {
    public static bool FindSubarrays(int[] nums) {
        for (int i = 0; i < nums.Length - 1; i++) {
            for (int j = i + 1; j < nums.Length - 1; j++) {
                if (nums[i] + nums[i + 1] == nums[j] + nums[j + 1]) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void Main() {
        int[] nums = {4, 2, 4};
        Console.WriteLine(FindSubarrays(nums));
    }
}

The Python solution uses list indices to check each adjacent element pair's sum for equality. It iterates through the entire list, returning True if a match is identified, or False otherwise.

Complexity

With time complexity at O(n^2) due to nested loops and space complexity at O(1) for the same reasons as other languages, this approach is straightforward but not optimal for large inputs.

Try this approach in the editor

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.

Python

def findSubarrays(nums):
    seen = set()
    for i in range(len(nums) - 1):
        sum_pair = nums[i] + nums[i + 1]
        if sum_pair in seen:
            return True
        seen.add(sum_pair)
    return False

nums = [4, 2, 4]
print(findSubarrays(nums))

Java

import java.util.HashSet;

public class SubarrayChecker {
    public static boolean findSubarrays(int[] nums) {
        HashSet<Integer> seen = new HashSet<>();
        for (int i = 0; i < nums.length - 1; i++) {
            int sum = nums[i] + nums[i + 1];
            if (seen.contains(sum)) {
                return true;
            }
            seen.add(sum);
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums = {4, 2, 4};
        System.out.println(findSubarrays(nums));
    }
}

C++

#include <unordered_set>
#include <vector>
#include <iostream>

using namespace std;

bool findSubarrays(vector<int>& nums) {
    unordered_set<int> sums;
    for (int i = 0; i < nums.size() - 1; i++) {
        int sum = nums[i] + nums[i + 1];
        if (sums.find(sum) != sums.end()) {
            return true;
        }
        sums.insert(sum);
    }
    return false;
}

int main() {
    vector<int> nums = {4, 2, 4};
    cout << (findSubarrays(nums) ? "true" : "false") << endl;
    return 0;
}

JavaScript

function findSubarrays(nums) {
    const seen = new Set();
    for (let i = 0; i < nums.length - 1; i++) {
        const sum = nums[i] + nums[i + 1];
        if (seen.has(sum)) {
            return true;
        }
        seen.add(sum);
    }
    return false;
}

const nums = [4, 2, 4];
console.log(findSubarrays(nums));

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

typedef struct HashSet {
    int *table;
    size_t size;
} HashSet;

HashSet* createHashSet(size_t size) {
    HashSet *set = (HashSet*)malloc(sizeof(HashSet));
    set->table = (int*)calloc(size, sizeof(int));
    set->size = size;
    return set;
}

void insert(HashSet *set, int value) {
    size_t index = abs(value) % set->size;
    while (set->table[index] != 0) {
        if (set->table[index] == value) return; // already exist
        index = (index + 1) % set->size;
    }
    set->table[index] = value;
}

bool contains(HashSet *set, int value) {
    size_t index = abs(value) % set->size;
    while (set->table[index] != 0) {
        if (set->table[index] == value) return true;
        index = (index + 1) % set->size;
    }
    return false;
}

bool findSubarrays(int* nums, int numsSize) {
    HashSet *set = createHashSet(numsSize);

    for (int i = 0; i < numsSize - 1; i++) {
        int sum = nums[i] + nums[i + 1];
        if (contains(set, sum)) {
            free(set->table);
            free(set);
            return true;
        }
        insert(set, sum);
    }

    free(set->table);
    free(set);
    return false;
}

int main() {
    int nums[] = {4, 2, 4};
    int size = sizeof(nums) / sizeof(nums[0]);
    printf("%s\n", findSubarrays(nums, size) ? "true" : "false");
    return 0;
}

using System;
using System.Collections.Generic;

public class SubarrayChecker {
    public static bool FindSubarrays(int[] nums) {
        HashSet<int> seen = new HashSet<int>();
        for (int i = 0; i < nums.Length - 1; i++) {
            int sum = nums[i] + nums[i + 1];
            if (seen.Contains(sum)) {
                return true;
            }
            seen.Add(sum);
        }
        return false;
    }

    public static void Main() {
        int[] nums = {4, 2, 4};
        Console.WriteLine(FindSubarrays(nums));
    }
}

The Python version uses a set to track sums, checking each pair only once. This pattern minimizes unnecessary duplication checks, making it concise and fast.

Complexity

Given O(n) time and space due to linear iterations and data structure usage, this approach is optimal for provided tasks.

Try this approach in the editor

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.

TypeScript

function findSubarrays(nums: number[]): boolean {
    const vis: Set<number> = new Set<number>();
    for (let i = 1; i < nums.length; ++i) {
        const x = nums[i - 1] + nums[i];
        if (vis.has(x)) {
            return true;
        }
        vis.add(x);
    }
    return false;
}

func findSubarrays(nums []int) bool {
	vis := map[int]bool{}
	for i, b := range nums[1:] {
		x := nums[i] + b
		if vis[x] {
			return true
		}
		vis[x] = true
	}
	return false
}

Rust

use std::collections::HashSet;
impl Solution {
    pub fn find_subarrays(nums: Vec<i32>) -> bool {
        let n = nums.len();
        let mut set = HashSet::new();
        for i in 1..n {
            if !set.insert(nums[i - 1] + nums[i]) {
                return true;
            }
        }
        false
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Brute Force Approach	With time complexity at O(n^2) due to nested loops and space complexity at O(1) for the same reasons as other languages, this approach is straightforward but not optimal for large inputs.
Optimized HashSet Approach	Given O(n) time and space due to linear iterations and data structure usage, this approach is optimal for provided tasks.
Hash Table	–

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

Frequently asked questions

Is Find Subarrays With Equal Sum easy or hard?

Find Subarrays With Equal Sum is categorized as an Easy problem. The main idea is recognizing that only adjacent pair sums matter and using a hash set to detect duplicates efficiently.

Find Subarrays With Equal Sum Python/Java solution

In Python, use a set to store pair sums while iterating through the array. In Java or C++, use HashSet or unordered_set respectively. The logic is identical: compute nums[i] + nums[i+1], check if it exists in the set, and insert it if not.

How to solve Find Subarrays With Equal Sum in O(n)?

Compute the sum of every adjacent pair while iterating through the array. Maintain a HashSet of previously seen sums. If the current pair sum already exists in the set, two different subarrays must have the same sum, so return true. Otherwise insert the sum and continue.

What is the best approach for Find Subarrays With Equal Sum?

The HashSet approach is the most efficient. Iterate through the array, compute each adjacent pair sum, and store it in a set. If the same sum appears again, two subarrays share the same total. This solution runs in O(n) time with O(n) extra space.

Is Find Subarrays With Equal Sum asked at Google/Amazon/Meta?

Problems involving duplicate detection with hash tables are common in interviews at companies like Amazon, Google, and Meta. While this exact question may vary, the pattern of storing computed values in a set for O(1) lookups appears frequently.

What data structure is used in Find Subarrays With Equal Sum?

A HashSet (or unordered set) is the main data structure in the optimal solution. It stores sums of adjacent pairs so duplicates can be detected in constant average time during a single pass through the array.

What is the time complexity of Find Subarrays With Equal Sum?

The optimal solution runs in O(n) time because the array is scanned once and each pair sum is inserted or checked in a hash set with average O(1) cost. A brute force comparison of all pairs of subarrays takes O(n^2) time.

Find Subarrays With Equal Sum solution and explanation

The problem

Approach overview

Approach 1: Brute Force Approach

Approach 2: Optimized HashSet Approach

Approach 3: Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find Subarrays With Equal Sum solution and explanation

The problem

Approach overview

Approach 1: Brute Force Approach

Approach 2: Optimized HashSet Approach

Approach 3: Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems