网站开发岗位职责及任职要求,高邮市城乡建设局网站,网站界面设计规范,苏州免费网站建设LC2908. 元素和最小的山形三元组 I
给你一个下标从 0 开始的整数数组 nums 。
如果下标三元组 (i, j, k) 满足下述全部条件#xff0c;则认为它是一个 山形三元组 #xff1a;
i j k nums[i] nums[j] 且 nums[k] nums[j] 请你找出 nums 中 元素和最小…LC2908. 元素和最小的山形三元组 I
给你一个下标从 0 开始的整数数组 nums 。
如果下标三元组 (i, j, k) 满足下述全部条件则认为它是一个 山形三元组
i j k nums[i] nums[j] 且 nums[k] nums[j] 请你找出 nums 中 元素和最小 的山形三元组并返回其 元素和 。如果不存在满足条件的三元组返回 -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 的山形三元组。 提示
3 nums.length 50 1 nums[i] 50
纯暴力代码
三重循环时间复杂度On^3
class Solution:def minimumSum(self, nums: List[int]) - int:n len(nums)ans inffor i in range(n):for j in range(i1,n):for k in range(j1,n):if nums[i]nums[j] and nums[j]nums[k]:ans min(ans,nums[i]nums[j]nums[k])return ans if ans!inf else -1枚举j的思路
也可以枚举j然后在内存分别枚举i和k这样时间复杂度是On^2
AC代码
预处理前后缀On 我们发现如果枚举j的前提下我还需要用On找到前缀/后缀的最小值其实这一步可以用预处理的方式在循环外部先计算出来最后再以O1去调用即可
class Solution:def minimumSum(self, nums: List[int]) - int:n len(nums)ans infl [inf]*nr [inf]*nmi inffor i in range(n):mi min(mi,nums[i])l[i] mimi inffor i in range(n-1,-1,-1):mi min(mi,nums[i])r[i] mifor i in range(1,n-1):lmi l[i-1]rmi r[i1]if lminums[i] and nums[i]rmi:ans min(ans,lmirminums[i])return ans if ans!inf else -1
