日期：2026年8月18日
LeetCode 題目連結：3471. Find the Largest Almost Missing Integer
解題想法
簡單題。題目給一個長度為 $n$ 的陣列 $nums$ 及整數 $k$，要從 $nums$ 之中找出長度為 $k$ 的連續子序列，子序列之中有一個數字只出現一次，回傳這些數字中的最大值。我一開始用的寫法非常直接，先找出所有長度為 $k$ 的連續子序列，將子序列存成 set，再將 set 存入 list 之中。接下來再依序從 $nums$ 讀取數字 $num$，檢查 $num$ 是否在所有的子序列中只出現一次而且 $num$ 大於目前的答案 $ans$，如果條件成立就更新 $ans$。這個寫法在 Python 的速度還可以，但是在 C++ 就很糟糕了。
比較好的寫法應該是列出以下 3 種狀況：
- $k = n$，子序列就是 $nums$，回傳 $nums$ 之中的最大值。
- $k = 1$，子序列就是 $nums$ 之中的每個數字，找出只在 $nums$ 之中出現一次的數字最大值。
- $k \neq n, k \neq 1$，只需要找 $nums[0]$ 與 $nums[n-1]$，因為中間的數字至少會出現在 2 個子序列之中。答案有 4 種：
- $nums[0]$ 與 $nums[n-1]$ 都只出現一次，回傳較大者。
- $nums[0]$ 只出現一次，$nums[n-1]$ 出現 2 次以上，回傳 $nums[0]$。
- $nums[n-1]$ 只出現一次，$nums[0]$ 出現 2 次以上，回傳 $nums[n-1]$。
- 以上條件皆不成立，回傳 $-1$。
Python 程式碼
方法1，Runtime: 3 ms, beats 62.30%. Memory: 19.15 MB, beats 93.85%.
class Solution:
def largestInteger(self, nums: List[int], k: int) -> int:
n = len(nums)
subs = [set() for _ in range(n-k+1)]
for i in range(n-k+1):
subs[i] = set(nums[i:i+k])
ans = -1
for num in nums:
cnt = 0
for sub in subs:
if num in sub: cnt += 1
if cnt >= 2: break
if cnt == 1 and num > ans:
ans = num
return ans
方法2，Runtime: 1 ms, beats 70.90%. Memory: 19.36 MB, beats 35.66%.
class Solution:
def largestInteger(self, nums: List[int], k: int) -> int:
n = len(nums) # 長度
# Case 1. k == n，回傳 nums 的最大值
if k == n: return max(nums)
# Case 2. k == 1，回傳只出現一次的數字最大值
cnt = Counter(nums) # 計數器
if k == 1:
ans = -1 # 答案預設為 -1
for num in nums:
if cnt[num] == 1 and num > ans:
ans = num
return ans
# Case 3. 一般狀況，只需要考慮 nums[0] 及 nums[n-1]，因為其它數字至少會出現在子序列之中 2 次
first, last = nums[0], nums[-1]
# first, last 次數都是 1，回傳較大者
if cnt[first] == 1 and cnt[last] == 1:
return max(first, last)
# first 次數 1，last 次數大於 1，回傳 first
if cnt[first] == 1 and cnt[last] > 1:
return first
# first 次數大於 1，last 次數 1，回傳 last
if cnt[first] > 1 and cnt[last] == 1:
return last
# 沒有答案，回傳 -1
return -1
