Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2395.html

2395. Find Subarrays With Equal Sum

  • Difficulty: Easy.
  • Related Topics: Array, Hash Table.
  • Similar Questions: Two Sum, Partition Equal Subset Sum, Find Two Non-overlapping Sub-arrays Each With Target Sum.

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

Solution (Java, C++, Python)

  • class Solution {
        public boolean findSubarrays(int[] nums) {
            HashSet set = new HashSet<>();
            for(int i = 0; i < nums.length - 1; i++) {
                int temp = nums[i] + nums[i + 1];
                if (set.contains(temp)) {
                    return true;
                } else {
                    set.add(temp);
                }
            }
            return false;
        }
    }
    
    ############
    
    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;
        }
    }
    
  • class Solution:
        def findSubarrays(self, nums: List[int]) -> bool:
            s = set()
            for a, b in pairwise(nums):
                if (v := a + b) in s:
                    return True
                s.add(v)
            return False
    
    ############
    
    # 2395. Find Subarrays With Equal Sum
    # https://leetcode.com/problems/find-subarrays-with-equal-sum/
    
    class Solution:
        def findSubarrays(self, nums: List[int]) -> bool:
            n = len(nums)
            
            seen = set()
            
            for i in range(n - 1):
                curr = nums[i] + nums[i + 1]
                
                if curr in seen:
                    return True
                
                seen.add(curr)
            
            return False
                    
    
    
  • 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;
        }
    };
    
  • 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
    }
    
  • 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;
    }
    
    
  • 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
        }
    }
    
    

Explain:

nope.

Complexity:

  • Time complexity : O(n).
  • Space complexity : O(n).

All Problems

All Solutions