LeetCode 2441. 與對應負數同時存在的最大正整數(哈希集合一次遍歷圖解)

2441. 與對應負數同時存在的最大正整數

題目描述

給你一個不包含任何零的整數陣列 nums,找出「自身與對應的負數都在陣列中存在」的最大正整數 k。

回傳正整數 k,如果不存在這樣的整數,回傳 -1。

範例 1

1
2
3
輸入:nums = [-1,2,-3,3]
輸出:3
解釋:3 是陣列中唯一一個滿足題目要求的 k。

範例 2

1
2
3
輸入:nums = [-1,10,6,7,-7,1]
輸出:7
解釋:陣列中存在 1 和 7 對應的負數,7 的值更大。

範例 3

1
2
3
輸入:nums = [-10,8,6,7,-2,-3]
輸出:-1
解釋:不存在滿足題目要求的 k,回傳 -1。

限制

  • 1 <= nums.length <= 1000
  • -1000 <= nums[i] <= 1000
  • nums[i] != 0

本題為第 315 場周賽 Q1。本文題解思路與程式碼整理自 LeetCode 題解作者灵茶山艾府,影片講解。圖解與步驟說明為自行補充。

前置知識:哈希集合

HashSet 只回答一件事:「這個數有沒有放進去過」,查詢與新增平均都是 O(1)。這題不需要知道每個數出現幾次,只需要知道「在不在」,所以用集合就夠了,不必用 Map 計數。

思路

把題目換成「找一對相反數」

「k 與 -k 都在陣列中」就是陣列裡有一對相反數 (k, -k)。要的是所有這樣的對裡,正數那一邊最大的那個 k。

為什麼一次遍歷就夠

一對相反數 a 與 -a 在陣列中會有先後。不論誰先誰後,後出現的那個走到時,先出現的那個已經在集合裡了。所以:

  1. 準備一個空的哈希集合 s,記錄已經遍歷過的數;ans = -1。
  2. 從左到右遍歷,設目前的數是 x。
  3. 如果 -x 在 s 裡,說明 x 和 -x 湊成一對,候選答案是 |x|(不管 x 是正是負,|x| 都是那個正整數 k),更新 ans = max(ans, |x|)。
  4. 把 x 加進 s。
  5. 遍歷結束回傳 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
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int findMaxK(int[] nums) {
int ans = -1;
var s = new HashSet<Integer>();
for (int x : nums) {
if (s.contains(-x)) {
ans = Math.max(ans, Math.abs(x));
}
s.add(x);
}
return ans;
}
}

補充說明(自行補充)

  • 為什麼先查再加:先查 -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/
作者
Dean Yang
發布於
2026年11月10日
許可協議