LeetCode 4074. 和為目標值的最大乘積對(枚舉右維護左圖解)

4074. 和為目標值的最大乘積對

題目描述

給你一個整數陣列 nums 和一個整數 target。

當一個由不同下標組成的二元組 (i, j) 滿足以下條件,稱它是有效的:

  • nums[i] + nums[j] == target
  • nums[i] > nums[j]

回傳一個有效的二元組 [i, j],使其乘積 nums[i] * nums[j] 在所有有效二元組中是最大的。如果不存在有效的二元組,回傳 [-1, -1]。

如果有多個有效二元組都能達到最大乘積,可以回傳其中的任意一個。

範例 1

1
2
3
4
5
6
輸入:nums = [1,2,3,4], target = 5
輸出:[2,1]
解釋:存在 2 個有效的二元組:
(3, 0):4 + 1 = 5,乘積 4
(2, 1):3 + 2 = 5,乘積 6
第二個二元組的乘積更大,所以答案是 [2, 1]。

範例 2

1
2
3
4
5
6
輸入:nums = [-3,-1,4,2], target = 1
輸出:[3,1]
解釋:存在 2 個有效的二元組:
(2, 0):4 + (-3) = 1,乘積 -12
(3, 1):2 + (-1) = 1,乘積 -2
由於 -2 > -12,因此答案是 [3, 1]。

範例 3

1
2
3
輸入:nums = [3,3,5], target = 6
輸出:[-1,-1]
解釋:nums[0] 和 nums[1] 的和雖然為 6,但它們是相等的,不滿足 nums[i] > nums[j]。

限制

  • 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 交換即可。

演算法

  1. 準備哈希表 pos,記錄「數 → 下標」;bestI = bestJ = -1。
  2. 從左到右遍歷,設目前的數是 x = nums[i]。
  3. 如果 x * 2 == target,表示 x == target - x,兩個數相等,不符合條件,直接跳過。
  4. 查 pos 有沒有 target - x。有的話,湊成一對,乘積是 x * (target - x)。如果它比目前最佳乘積大(或還沒有答案),更新 bestI = i、bestJ = 配對的下標。
  5. 把 x → i 放進 pos。
  6. 遍歷結束,如果有答案且 nums[bestI] < nums[bestJ],交換兩個下標,確保 nums[i] > nums[j]。
  7. 回傳 [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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public int[] maxProductPair(int[] nums, int target) {
Map<Integer, Integer> pos = new HashMap<>();
int bestI = -1;
int bestJ = -1;
for (int i = 0; i < nums.length; i++) {
int x = nums[i];
if (x * 2 == target) { // x = target-x
continue;
}
Integer j = pos.get(target - x);
if (j != null && (bestI < 0 || x * (target - x) > nums[bestI] * (target - nums[bestI]))) { // 也可以比誰離 target/2 更近
bestI = i;
bestJ = j;
}
pos.put(x, i);
}

if (bestI >= 0 && nums[bestI] < nums[bestJ]) {
// 保證 nums[bestI] > nums[bestJ]
int tmp = bestI;
bestI = bestJ;
bestJ = tmp;
}
return new int[]{bestI, bestJ};
}
}

補充說明(自行補充)

  • 為什麼跳過時連 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/
作者
Dean Yang
發布於
2026年11月10日
許可協議