“This is the ninth day of my participation in the First Challenge 2022. For details: First Challenge 2022”

preface

Participated in the 70th biweekly competition, the topic is still a little difficult, the list of the first four questions completed in 17 minutes, the previous weekly competition first place only 7 or 8 minutes ended. This is the second question of the Biweekly Contest 70, the difficulty Medium, actually is to find a regular question, feel that there is no investigation point.

describe

You are given a 0-indexed array of n integers differences, which describes the differences between each pair of consecutive integers of a hidden sequence of length (n + 1). More formally, call the hidden sequence hidden, then we have that differences[i] = hidden[i + 1] – hidden[i].

You are further given two integers lower and upper that describe the inclusive range of values [lower, upper] that the hidden sequence can contain.

  • For example, given differences = [1, -3, 4], lower = 1, upper = 6, the hidden sequence is a sequence of length 4 whose elements are in between 1 and 6 (inclusive).
  • [3, 4, 1, 5] and [4, 5, 2, 6] are possible hidden sequences.
  • [5, 6, 3, 7] is not possible since it contains an element greater than 6.
  • [1, 2, 3, 4] is not possible since the differences are not correct.

Return the number of possible hidden sequences there are. If there are no possible sequences, return 0.

Example 1:

Input: differences = [1,-3,4], lower = 1, upper = 6
Output: 2
Explanation: The possible hidden sequences are:
- [3, 4, 1, 5]
- [4, 5, 2, 6]
Thus, we return 2.
Copy the code

Note:

n == differences.length
1 <= n <= 10^5
-10^5 <= differences[i] <= 10^5
-10^5 <= lower <= upper <= 10^5
Copy the code

parsing

Given a 0 index array difference containing n integers, it describes the difference between each pair of consecutive integers hidden in a hidden sequence of length N + 1. Differences [I] = hidden[I + 1] – hidden[I]. Two integers lower and upper are also given, which describe the values hidden can contain in the range [lower, upper]. Returns the number of hidden sequences that may exist. If there is no possible sequence, 0 is returned.

  • For example, given differences = [1, -3, 4], lower = 1, upper = 6, the hidden sequence is a sequence of length 4 with elements between 1 and 6.
  • [3, 4, 1, 5] and [4, 5, 2, 6] are possible hidden sequences.
  • [5, 6, 3, 7] is impossible because it contains elements greater than 6.
  • [1, 2, 3, 4] is impossible because the difference is not correct.

The maximum value of differences. Length is 10^5, and the violent solution requires two cycles with time complexity O(n^2), which is bound to time out. This condition is the limitation that we must use the solution within O(n) or even O(1), and we must find a rule to solve the problem:

  • First, we find that the absolute value of difference in differences must be less than or equal to upper-lower, otherwise the corresponding hidden cannot appear
  • We found that after each differences is one of the elements minus one element before the difference, we traverse and calculation time, can get after a further element and how much is the first element of difference, so that all of the elements have relationship with the size of the first element, so we will be the topic into the scope of the first element, As long as the value of the first element is within a reasonable range, the whole hidden element must be reasonable. Reasonable here means that hidden elements are in the range of [lower, upper] and do not repeat.
  • In the newly obtained differences, we can find the maximum and minimum values d_mn and d_mx, which respectively represent the most and least distance from the first element in hidden. In this way, we know that the minimum optional value of the first element is Max (lower, lower-d_mn), and the maximum optional value is min(upper, upper-d_mx). The number of optional values of the first element, namely the number of possible sequences of hidden, can be obtained by direct counting.

In fact, this problem is very easy to solve calmly, but I tried to optimize the violent solution during the competition, which wasted a lot of time. Only when I saw the restrictions did I give up the violent solution and go to find the rule, so I still need to calmly look at the problem, anxious to write the code is useless.

answer

class Solution(object):
    def numberOfArrays(self, differences, lower, upper):
        """
        :type differences: List[int]
        :type lower: int
        :type upper: int
        :rtype: int
        """
        if max(abs(min(differences)), abs(max(differences))) > upper - lower:
            return 0
        n = len(differences)
        for i in range(1,n):
            differences[i] = differences[i-1] + differences[i]
        result = 0
        d_mn = min(differences)
        d_mx = max(differences)
        N = max(lower, lower-d_mn)
        M = min(upper, upper-d_mx)
        for i in range(N, M+1):
            result += 1
        return result
Copy the code

The results

82/82 Test cases passed. Status: Accepted Runtime: 1461 MS Memory Usage: 26.3 MBCopy the code

The original link

Leetcode.com/contest/biw…

Your support is my biggest motivation