はじめに

整数の配列から、2 値の合計が等しい 2 つのサブ配列があるか調べよ、という問題。 nums = [4,2,4] なら、インデックス ([0, 1], [1, 2]) が該当するため、真。 ここで、以下の制約の通り、サブ配列とは連続したインデックスであることが保証されており、単に隣り合うインデックス同士を足した結果を走査するだけでよい。

A subarray is a contiguous non-empty sequence of elements within an array.

https://leetcode.com/problems/find-subarrays-with-equal-sum/description/

初手

久しぶりに 5 分程度で解けました。制約の通り、隣り合うインデックスの合計を map に保存しておき、過去に同じ合計が存在すれば true です。もうそれだけです。時間計算量は O(n) で、Beats 100% です。

https://leetcode.com/problems/find-subarrays-with-equal-sum/submissions/1624846018

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func findSubarrays(nums []int) bool {
    m := make(map[int]bool, 1000)
    for i := 0; i < len(nums) - 1; i++ {
        sum := nums[i] + nums[i+1]
        if m[sum] {
            return true
        }
        m[sum] = true
    }
    return false
}

Solutions を見ても異なる考え方が見つからないため、この問題はこれだけ。