LeetCode 4074. 和為目標值的最大乘積對(枚舉右維護左圖解)
4074. 和為目標值的最大乘積對
題目描述
給你一個整數陣列 nums 和一個整數 target。
當一個由不同下標組成的二元組 (i, j) 滿足以下條件,稱它是有效的:
nums[i] + nums[j] == targetnums[i] > nums[j]
回傳一個有效的二元組 [i, j],使其乘積 nums[i] * nums[j] 在所有有效二元組中是最大的。如果不存在有效的二元組,回傳 [-1, -1]。
如果有多個有效二元組都能達到最大乘積,可以回傳其中的任意一個。
範例 1
1 | |
範例 2
1 | |
範例 3
1 | |
限制
2 <= nums.length <= 100-100 <= nums[i], target <= 100
本題為第 193 場雙週賽 Q1。本文題解思路與程式碼整理自 LeetCode 題解作者灵茶山艾府,影片講解。圖解與步驟說明為自行補充。
前置知識:枚舉右,維護左
要找「兩個位置」配成一對,可以只枚舉其中一個(右邊那個),把左邊已經看過的資訊記在哈希表裡,用 target - x 一次查出配對的另一個。這個套路和 LeetCode 1512、LeetCode 2441 相同,這題的哈希表要記的是「每個數出現的下標」,因為答案要回傳下標。
思路
先把條件簡化
題目要求 nums[i] > nums[j],但不要求 i < j。所以 i、j 誰在左邊都可以:
- 兩個數
a、b和為target,且a != b,就一定有一個比較大。大的那個當i,小的當j,條件就滿足了。 - 因此「有效」其實只剩兩件事:兩個數的和是
target,而且兩個數不相等(nums[i] == nums[j]不行)。 - 找到配對後,如果發現
nums[i] < nums[j],把i和j交換即可。
演算法
- 準備哈希表
pos,記錄「數 → 下標」;bestI = bestJ = -1。 - 從左到右遍歷,設目前的數是
x = nums[i]。 - 如果
x * 2 == target,表示x == target - x,兩個數相等,不符合條件,直接跳過。 - 查
pos有沒有target - x。有的話,湊成一對,乘積是x * (target - x)。如果它比目前最佳乘積大(或還沒有答案),更新bestI = i、bestJ = 配對的下標。 - 把
x → i放進pos。 - 遍歷結束,如果有答案且
nums[bestI] < nums[bestJ],交換兩個下標,確保nums[i] > nums[j]。 - 回傳
[bestI, bestJ]。
小提醒:乘積 x * (target - x) 是開口向下的拋物線,在 x = target / 2 時最大,所以也可以改成比較誰離 target / 2 更近,不必真的乘(題解註解提到的另一種寫法)。
圖解(可互動)
預設是範例 2,過程中會遇到「找到配對且乘積更大,更新 best」。另一個按鈕是自編範例 nums = [5,3,1,4]、target = 6,可以看到 3 × 2 = 6 的情況被跳過,以及最後要交換 i、j 的情況。
範例:
nums(i 為目前枚舉的位置)
x = nums[i]—
target − x 在 Map 裡嗎?—
best(i, j)[−1, −1]
解法(灵茶山艾府)
1 | |
補充說明(自行補充)
- 為什麼跳過時連
pos.put也不做:x == target - x的數不可能和任何數配成有效的對(要配的另一半就是它自己的值,兩者相等),之後的數查target - y若剛好等於它,也是「相等」的情況,同樣無效,所以放不放都不影響。 - 同一個數出現多次:
pos.put會用較新的下標覆蓋,只要乘積相同,題目允許回傳任意一個,所以不影響正確性。 - 範例 3 的
[3,3,5]:3 * 2 == 6,兩個 3 都被跳過,5查1也找不到,沒有配對,回傳[-1,-1]。
複雜度分析
- 時間複雜度:O(n),其中 n 是
nums的長度。每個數只處理一次,哈希表讀寫平均 O(1)。 - 空間複雜度:O(n),哈希表最多存 n 個數。
相似題目
題解提到,專題訓練見作者整理的資料結構題單「§0.1 枚舉右,維護左」。題單沒有給網址,這裡不放連結。
LeetCode 4074. 和為目標值的最大乘積對(枚舉右維護左圖解)
https://shengshengyang.github.io/2026/11/10/leetcode-4074-max-product-pair-sum-target/