ETH官方钱包

前往
大廳
主題

LeetCode - 2395. Find Subarrays With Equal Sum 解題心得

Not In My Back Yard | 2023-07-24 12:00:05 | 巴幣 0 | 人氣 128

題目連結:


題目意譯:
給定一個索引值從 0 開始的整數陣列 nums,請決定出是否存在兩個長度 2 且各自總和相同的子陣列。注意到這兩個子陣列必須開始於不同的索引值。

如果這些子陣列存在則回傳真(True);反之,回傳假(False)。

一個子陣列為一個陣列中的連續非空元素序列。

限制:
2 ≦ nums.length ≦ 1000
-10 ^ 9 ≦ nums[i] ≦ 10 ^ 9



範例測資:
範例 1:
輸入: nums = [4,2,4]
輸出: true
解釋: 有著元素 [4,2] 和 [2,4] 的兩子陣列有著相同的總和值 6。

範例 2:
輸入: nums = [1,2,3,4,5]
輸出: false
解釋: 沒有大小 2 的兩個子陣列擁有相同的總和值。

範例 3:
輸入: nums = [0,0,0]
輸出: true
解釋: 子陣列 [nums[0],nums[1]] 和 [nums[1],nums[2]] 有著相同的總和值 6。
注意到兩個子陣列的內容是相同的,因為兩者在原始陣列中位於不同位置,因而視為不同。


解題思維:
可以看到大小為 2 的子陣列即為相鄰的兩個數字。因此我們可以直接窮舉出所有相鄰數字對。接著有很多方式可以解開本題:
一:如範例程式碼所示,用一個雜湊表(Hash Table)來統計某一種總和值有沒有出現過。當有一個總和值出現第二次,則代表存在至少兩個「不同」的數對可以得到一樣的總和值;反之則否。

二:每個數對總和值去與其他每個數對總和值比較看看即可。

三:把所有總和值丟到一個陣列並排序(小到大或大到小都可),而一樣的總和值會排在彼此附近,所以掃過一次檢查有沒有相鄰總和值一樣即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

追蹤 創作集

作者相關創作

更多創作