【LeetCode周赛】LeetCode第365场周赛

有序三元组中的最大值 I

给你一个下标从 0 开始的整数数组nums。
请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。
下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。

示例 1：

输入：nums = [12,6,1,2,7]
输出：77
解释：下标三元组 (0, 2, 4) 的值是 (nums[0] -nums[2]) * nums[4] = 77 。 可以证明不存在值大于 77 的有序下标三元组。

示例 2：

输入：nums = [1,10,3,4,19]
输出：133
解释：下标三元组 (1, 2, 4) 的值是 (nums[1] -nums[2]) * nums[4] = 133 。 可以证明不存在值大于 133 的有序下标三元组。

示例 3：

输入：nums = [1,2,3]
输出：0
解释：唯一的下标三元组 (0, 1, 2) 的值是一个负数，(nums[0] -nums[1]) * nums[2] = -3 。因此，答案是 0 。

提示：
$3<=nums.length<=100$
$1<=nums[i]<=10^6$

分析：
根据数据范围可以发现，$nums.length$最大也只是100，因此可以直接按照题意，暴力枚举满足题意的$i,j,k$三个位置的数，计算出$(nums[i]-nums[j])\ast nums[k]$的值，用ans维护最大值即可。时间复杂度$O(n^3)$

代码：

class Solution {
public:
    long long maximumTripletValue(vector<int>& nums) {
        int n=nums.size();
        long long ans=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                for(int k=j+1;k<n;k++){
                    ans=max(ans,(long long)(nums[i]-nums[j])*nums[k]);
                }
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

有序三元组中的最大值 II

给你一个下标从 0 开始的整数数组nums。
请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。
下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。

示例 1：

输入：nums = [12,6,1,2,7]
输出：77
解释：下标三元组 (0, 2, 4) 的值是 (nums[0] -nums[2]) * nums[4] = 77 。 可以证明不存在值大于 77 的有序下标三元组。

示例 2：

输入：nums = [1,10,3,4,19]
输出：133
解释：下标三元组 (1, 2, 4) 的值是 (nums[1] -nums[2]) * nums[4] = 133 。 可以证明不存在值大于 133 的有序下标三元组。

示例 3：

输入：nums = [1,2,3]
输出：0
解释：唯一的下标三元组 (0, 1, 2) 的值是一个负数，(nums[0] -nums[1]) * nums[2] = -3 。因此，答案是 0 。

提示：
$3<=nums.length<=10^5$
$1<=nums[i]<=10^6$

分析：
此题为有序三元组中的最大值I的加强版，即数据范围变大了，不可以在使用暴力$O(n^3)$的方法完成。我们只能在$O(n)$的时间复杂度下完成此题。
不难发现，要使得这个有序下标三元组最大，对于$j$位置的数来说，$i$和$k$位置的数都是越大越好，发现了这一点，后续就好处理了。只需要维护每一个$j$位置的前缀最大值$pre[j]$和后缀最大值$suf[j]$，以当前$j$位置作为下标三元组中间位置的最大值即为$(pre[j]-nums[j])\ast suf[j]$。即可在线性时间复杂度内完成该题目。
代码：

class Solution {
public:
    long long maximumTripletValue(vector<int>& nums) {
        //记录数组前面和后面的最大数
        int n=nums.size();
        vector<int>pre(n+1),suf(n+1);
        int ma=0;
        for(int i=0;i<n;i++){
            pre[i]=ma;
            ma=max(ma,nums[i]);
        }
        ma=0;
        for(int i=n-1;i>=0;i--){
            suf[i]=ma;
            ma=max(ma,nums[i]);
        }
        long long ans=0;
        for(int i=1;i<n-1;i++){//枚举中间的那个数字
            ans=max((long long)(pre[i]-nums[i])*suf[i],ans);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

无限数组的最短子数组

给你一个下标从 0 开始的数组 nums 和一个整数 target 。
下标从 0 开始的数组 infinite_nums 是通过无限地将 nums 的元素追加到自己之后生成的。
请你从 infinite_nums 中找出满足 元素和 等于 target 的 最短 子数组，并返回该子数组的长度。如果不存在满足条件的子数组，返回 -1 。

示例 1：

输入：nums = [1,2,3], target = 5
输出：2
解释：在这个例子中 infinite_nums =[1,2,3,1,2,3,1,2,…] 。 区间 [1,2] 内的子数组的元素和等于 target = 5 ，且长度 length = 2 。 可以证明，当元素和等于目标值 target = 5 时，2 是子数组的最短长度。

示例 2：

输入：nums = [1,1,1,2,3], target = 4
输出：2
解释：在这个例子中 infinite_nums =[1,1,1,2,3,1,1,1,2,3,1,1,…]. 区间 [4,5] 内的子数组的元素和等于 target = 4 ，且长度length = 2 。 可以证明，当元素和等于目标值 target = 4 时，2 是子数组的最短长度。

示例 3：

输入：nums = [2,4,6,8], target = 3
输出：-1
解释：在这个例子中 infinite_nums =[2,4,6,8,2,4,6,8,…] 。 可以证明，不存在元素和等于目标值 target = 3 的子数组。

提示：
$1<=nums.length<=10^5$
$1<=nums[i]<=10^5$
$1<=target<=10^9$

分析：
题目需要计算一个$infinit{e}_{n}ums$数组中是否能够组成和为$target$的值，我们可以想到，如果$target$能够被构成，则其是被$k$个$nuns$数组的和$sum$以及一个余数$v$构成，即$target=k\ast sum+v,k>=0,0<=v<sum$。
所以我们主要讨论的是$v$这个数字能否被$infinit{e}_{n}ums$数组构造出来，因为v是target除以sum的余数，所以$v<sum$，因此，如果v能够被构造出来，其肯定是在两个nums数组中的一段数字，且长度不超过n(只用考虑两个nums数组就可以考虑到从nums数组末加到nums数组开头)。
所以可以用双指针来对两个nums数组连接起来的数组进行构造，在右指针移动的同时，一旦当前和total>v，则左指针移动，最终维护一个构造出v值的最短子数组长度。
代码：

class Solution {
public:
    int minSizeSubarray(vector<int>& nums, int target) {
        int n=nums.size();
        long long sum=0;
        for(int i=0;i<n;i++)sum+=nums[i];
        int p=target/sum;//至少需要这么多个完整的数组
        int v=target%sum;//剩下的值，需要从剩下的两个数组中组成
        int total=0,minn=n;
        for(int left=0,right=0;right<2*n;right++){
            total+=nums[right%n];
            while(total>v)total-=nums[left%n],left++;
            if(total==v)minn=min(minn,right-left+1);
        }
        if(minn==n)return -1;
        return p*n+minn;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18