algoadvance

Leetcode 2395. Find Subarrays With Equal Sum

Problem Statement

You are 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 start at different indices.

Formally, return true if there exist two indices i and j (i != j) such that nums[i] + nums[i + 1] == nums[j] + nums[j + 1], and return false otherwise.

Clarifying Questions

  1. Constraints on the array length and values?
    • The length of the array is between 2 and 1000 inclusive.
    • The elements of the array are integers between -10^5 and 10^5 inclusive.
  2. Can subarrays overlap?
    • No, subarrays should start at different indices, so they cannot overlap.

Strategy

  1. Iterate through the array to calculate sums of all subarrays of length 2.
  2. Use a set to store sums that have been encountered.
  3. While iterating, check if the current subarray sum already exists in the set:
    • If it does, return true since we have found two subarrays with the same sum.
    • If it does not, add the sum to the set.
  4. If the iteration completes without finding any matching sums, return false.

Code

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

bool findSubarraysWithEqualSum(const std::vector<int>& nums) {
    std::unordered_set<int> sums;
    
    for (size_t 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;
}

// Example usage
int main() {
    std::vector<int> nums1 = {4, 2, 4};
    std::vector<int> nums2 = {1, 2, 3, 4, 5};
    
    std::cout << std::boolalpha;
    std::cout << "Test case 1: " << findSubarraysWithEqualSum(nums1) << std::endl;  // Output: true
    std::cout << "Test case 2: " << findSubarraysWithEqualSum(nums2) << std::endl;  // Output: false
    
    return 0;
}

Time Complexity

This solution efficiently identifies whether there exist two subarrays with equal sums by leveraging a set to track previously encountered sums, ensuring quick look-up times.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI