Easy

题目描述

给你一个下标从 0 开始的整数数组 nums。

如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个 山形三元组：

  • i < j < k
  • nums[i] < nums[j] 且 nums[k] < nums[j]

请你找到所有山形三元组的 最小可能和，并返回这个 最小和。如果不存在满足条件的三元组，请返回 -1。

示例 1：

输入：nums = [8,6,1,5,3]
输出：9
解释：三元组 (2, 3, 4) 是一个和为 9 的山形三元组，因为：
- 2 < 3 < 4
- nums[2] < nums[3] 且 nums[4] < nums[3]
这个三元组的和是 nums[2] + nums[3] + nums[4] = 9。可以证明不存在和小于 9 的山形三元组。

示例 2：

输入：nums = [5,4,8,7,10,2]
输出：13
解释：三元组 (1, 3, 5) 是一个和为 13 的山形三元组，因为：
- 1 < 3 < 5
- nums[1] < nums[3] 且 nums[5] < nums[3]
这个三元组的和是 nums[1] + nums[3] + nums[5] = 13。可以证明不存在和小于 13 的山形三元组。

示例 3：

输入：nums = [6,5,4,3,4,5]
输出：-1
解释：可以证明 nums 中不存在山形三元组。

提示：

  • 3 <= nums.length <= 50
  • 1 <= nums[i] <= 50

解题思路

解题思路

这道题要求找到满足山形条件的三元组的最小和。山形三元组需要满足：i < j < k 且 nums[i] < nums[j] 且 nums[k] < nums[j]，即中间元素是三个元素中的最大值。

方法一：暴力枚举（推荐）

由于数组长度最多为50，我们可以直接暴力枚举所有可能的三元组。具体步骤：

  1. 使用三层循环遍历所有可能的 (i, j, k)，其中 i < j < k
  2. 检查是否满足山形条件：nums[i] < nums[j] 且 nums[k] < nums[j]
  3. 如果满足条件，计算三元组的和，并更新最小值
  4. 如果没有找到任何满足条件的三元组，返回-1

时间复杂度为 O(n³)，由于 n ≤ 50，这个复杂度完全可以接受。

方法二：优化枚举

我们也可以固定中间元素 j，然后在左侧找最小的满足 nums[i] < nums[j] 的元素，在右侧找最小的满足 nums[k] < nums[j] 的元素。这样可以将复杂度优化到 O(n²)，但对于此题的数据规模，差别不大。

代码实现

class Solution {
public:
    int minimumSum(vector<int>& nums) {
        int n = nums.size();
        int minSum = INT_MAX;
        bool found = false;
        
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] < nums[j] && nums[k] < nums[j]) {
                        found = true;
                        minSum = min(minSum, nums[i] + nums[j] + nums[k]);
                    }
                }
            }
        }
        
        return found ? minSum : -1;
    }
};

class Solution:
    def minimumSum(self, nums: List[int]) -> int:
        n = len(nums)
        min_sum = float('inf')
        found = False
        
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                for k in range(j + 1, n):
                    if nums[i] < nums[j] and nums[k] < nums[j]:
                        found = True
                        min_sum = min(min_sum, nums[i] + nums[j] + nums[k])
        
        return min_sum if found else -1

public class Solution {
    public int MinimumSum(int[] nums) {
        int n = nums.Length;
        int minSum = int.MaxValue;
        bool found = false;
        
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] < nums[j] && nums[k] < nums[j]) {
                        found = true;
                        minSum = Math.Min(minSum, nums[i] + nums[j] + nums[k]);
                    }
                }
            }
        }
        
        return found ? minSum : -1;
    }
}

var minimumSum = function(nums) {
    const n = nums.length;
    let minSum = Infinity;
    let found = false;
    
    for (let i = 0; i < n - 2; i++) {
        for (let j = i + 1; j < n - 1; j++) {
            for (let k = j + 1; k < n; k++) {
                if (nums[i] < nums[j] && nums[k] < nums[j]) {
                    found = true;
                    minSum = Math.min(minSum, nums[i] + nums[j] + nums[k]);
                }
            }
        }
    }
    
    return found ? minSum : -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

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

相关题目