Easy

题目描述

给你一个整数数组 nums。

从 nums 中选择三个不同下标的元素 a、b 和 c，使得表达式 a + b - c 的值最大。

返回这个表达式可能的最大值。

示例 1：

输入：nums = [1,4,2,5]
输出：8
解释：
我们可以选择 a = 4, b = 5, c = 1。表达式的值是 4 + 5 - 1 = 8，这是可能的最大值。

示例 2：

输入：nums = [-2,0,5,-2,4]
输出：11
解释：
我们可以选择 a = 5, b = 4, c = -2。表达式的值是 5 + 4 - (-2) = 11，这是可能的最大值。

提示：

  • 3 <= nums.length <= 100
  • -100 <= nums[i] <= 100
  • a 和 b 应该是 nums 中最大的两个值
  • c 应该是 nums 中的最小值

解题思路

这道题要求最大化表达式 a + b - c，其中 a、b、c 是数组中三个不同下标的元素。

核心思路： 要使 a + b - c 最大，我们需要：

  1. a 和 b 尽可能大（因为它们是加数）
  2. c 尽可能小（因为它是被减数）

贪心策略：

  • 选择数组中最大的两个不同元素作为 a 和 b
  • 选择数组中最小的元素作为 c
  • 需要确保 a、b、c 的下标不同

实现方法：

  1. 排序法（推荐）：将数组排序，最大的两个元素在末尾，最小的在开头
  2. 一次遍历法：记录最大值、次大值和最小值及其位置

由于数组长度最大为100，两种方法的性能差异不大，排序法代码更简洁清晰。

需要注意的边界情况：

  • 当最小值和最大值（或次大值）是同一个下标时，需要特殊处理
  • 数组中可能有重复元素，但我们需要的是不同下标

代码实现

class Solution {
public:
    int maximizeExpressionOfThree(vector<int>& nums) {
        int n = nums.size();
        int maxVal = INT_MIN;
        
        // 尝试所有可能的三元组
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if (i != j && j != k && i != k) {
                        maxVal = max(maxVal, nums[i] + nums[j] - nums[k]);
                    }
                }
            }
        }
        
        return maxVal;
    }
};

class Solution:
    def maximizeExpressionOfThree(self, nums: List[int]) -> int:
        n = len(nums)
        max_val = float('-inf')
        
        # 尝试所有可能的三元组
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    if i != j and j != k and i != k:
                        max_val = max(max_val, nums[i] + nums[j] - nums[k])
        
        return max_val

public class Solution {
    public int MaximizeExpressionOfThree(int[] nums) {
        int n = nums.Length;
        int maxVal = int.MinValue;
        
        // 尝试所有可能的三元组
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if (i != j && j != k && i != k) {
                        maxVal = Math.Max(maxVal, nums[i] + nums[j] - nums[k]);
                    }
                }
            }
        }
        
        return maxVal;
    }
}

var maximizeExpressionOfThree = function(nums) {
    const n = nums.length;
    let maxVal = -Infinity;
    
    // 尝试所有可能的三元组
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            for (let k = 0; k < n; k++) {
                if (i !== j && j !== k && i !== k) {
                    maxVal = Math.max(maxVal, nums[i] + nums[j] - nums[k]);
                }
            }
        }
    }
    
    return maxVal;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n³)三重循环遍历所有可能的三元组
空间复杂度O(1)只使用常数额外空间