Leetcode 454周赛

(Updated: )
# Leetcode 454周赛

Q2 统计特殊三元组#

Q2 统计特殊三元组

O(n) 级别的计数思路，核心是“把 j 当作中点，把满足条件的 i 累积到左侧计数表，把满足条件的 k 累积到右侧计数表”，从而避免三重循环。

对每一个下标 j ，只要知道

  • 左侧有多少个 i 满足 nums[i] = 2 × nums[j]
  • 右侧有多少个 k 满足 nums[k] = 2 × nums[j]

那么以 j 为中心能形成的三元组数就是二者乘积。

代码如下:

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
constexpr int MOD = 1e9 + 7;
class Solution
{
public:
  int specialTriplets(vector<int> &nums)
  {
    unordered_map<int64_t, int> left, right;
    
    for (int num : nums)
      right[num]++;
    
    int64_t ans = 0;
    for (int i = 0; i < nums.size(); i++) {
      right[nums[i]] -- ;
      int64_t target = nums[i] * 2;
      auto l_cnt = left.find(target);
      auto right_cnt = right.find(target);
      if (l_cnt != left.end() && right_cnt != right.end()) {
        ans += static_cast<int64_t>(l_cnt->second) * right_cnt->second;
        ans %= MOD;
      }
      left[nums[i]]++;
    }
    return static_cast<int>(ans);
  }
};

Q3 子序列首尾元素的最大乘积#

子序列首尾元素的最大乘积

对每一个作为右边界的下标 j，去找所有 足够靠左（i ≤ j-(m-1)）的位置里“最极端的两个数”：一个是该范围内最大的正/整体最大值 ，另一个是最小的负/整体最小值 。所以整个过程只需要维护两个前缀的极值表即可。

当然对于m=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
28
29
30
31
32
33
34
35
36
class Solution {
public:
    static constexpr int64_t INF = (1LL<<62);

    long long maximumProduct(vector<int>& nums, int m) {
        if (m == 1) {
          // 求出数组中的abs最大值就可以了
          long long ans = 0;
          for (int num : nums) {
            ans = max(ans, static_cast<long long>(1LL * num * num));
          }
          return ans;
        }

        // 维护两个前缀和数组
        vector<int> preMax(nums.size(), 0);
        vector<int> preMin(nums.size(), 0);
        preMax[0] = nums[0];
        preMin[0] = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            preMax[i] = max(preMax[i - 1], nums[i]);
            preMin[i] = min(preMin[i - 1], nums[i]);
        }
        long long ans = -INF;
        // 编译数组，先确认一个右侧边界
        for (int i = m-1; i < nums.size(); ++i) {
            // 最开头的距离为
            int left = i - m + 1;
            // 计算当前的最大值和最小值
            long long c1 = 1LL * preMax[left] * nums[i];
            long long c2 = 1LL * preMin[left] * nums[i];
            ans = max(ans, max(c1, c2));
        }
        return ans;
    }
};