LeetCode 2441. 與對應負數同時存在的最大正整數(哈希集合一次遍歷圖解)
2441. 與對應負數同時存在的最大正整數
題目描述
給你一個不包含任何零的整數陣列 nums,找出「自身與對應的負數都在陣列中存在」的最大正整數 k。
回傳正整數 k,如果不存在這樣的整數,回傳 -1。
範例 1
1 | |
範例 2
1 | |
範例 3
1 | |
限制
1 <= nums.length <= 1000-1000 <= nums[i] <= 1000nums[i] != 0
本題為第 315 場周賽 Q1。本文題解思路與程式碼整理自 LeetCode 題解作者灵茶山艾府,影片講解。圖解與步驟說明為自行補充。
前置知識:哈希集合
HashSet 只回答一件事:「這個數有沒有放進去過」,查詢與新增平均都是 O(1)。這題不需要知道每個數出現幾次,只需要知道「在不在」,所以用集合就夠了,不必用 Map 計數。
思路
把題目換成「找一對相反數」
「k 與 -k 都在陣列中」就是陣列裡有一對相反數 (k, -k)。要的是所有這樣的對裡,正數那一邊最大的那個 k。
為什麼一次遍歷就夠
一對相反數 a 與 -a 在陣列中會有先後。不論誰先誰後,後出現的那個走到時,先出現的那個已經在集合裡了。所以:
- 準備一個空的哈希集合
s,記錄已經遍歷過的數;ans = -1。 - 從左到右遍歷,設目前的數是
x。 - 如果
-x在s裡,說明x和-x湊成一對,候選答案是|x|(不管x是正是負,|x|都是那個正整數k),更新ans = max(ans, |x|)。 - 把
x加進s。 - 遍歷結束回傳
ans。
圖解(可互動)
用範例 2 nums = [-1,10,6,7,-7,1]。每個 j 走兩步:先查 -x 在不在集合(綠色格是先出現的那個相反數),再把 x 放進集合。留意最後一步:x = 1 也找到相反數 -1,但候選 1 比目前的 7 小,所以 ans 不變。
nums = [-1,10,6,7,-7,1]
x = nums[j]—
−x 在集合裡嗎?—
ans(最大的 k)−1
解法(灵茶山艾府)
1 | |
補充說明(自行補充)
- 為什麼先查再加:先查
-x、再加入x,查詢時集合裡只有x左邊的數。這題保證nums[i] != 0,所以x和-x不可能是同一個數,先加入再查結果也一樣;但如果題目允許 0,先加入會讓 0 自己配對自己,順序就要小心。 - 為什麼用
Math.abs(x):x可能是負數,走到-7時查到7在集合裡,候選答案是 7,不是 -7。
複雜度分析
- 時間複雜度:O(n),其中 n 是
nums的長度。每個數只處理一次。 - 空間複雜度:O(n),集合最多存 n 個數。
LeetCode 2441. 與對應負數同時存在的最大正整數(哈希集合一次遍歷圖解)
https://shengshengyang.github.io/2026/11/10/leetcode-2441-largest-positive-integer-with-negative/