"Interview high frequency question" is 1.5/5 difficult, and the classic "prefix and + dichotomy" application question

Title Description

This is a LeetCode Upper  209. Subarray with the smallest length  , The difficulty is   secondary .

Tag : 「 The prefix and 」、「 Two points 」

Given a containing n An array of positive integers and a positive integer target.

Find the sum of the array ≥ target The smallest length of Continuous subarray [numsl,numsl+1,...,numsr−1,numsr][nums_l, nums_{l+1}, ..., nums_{r-1}, nums_r][numsl,numsl+1​,...,numsr−1​,numsr​] , And return its length . If there is no sub array that meets the conditions , return 000 .

Example 1：

 Input ：target = 7, nums = [2,3,1,2,4,3]

 Output ：2

 explain ： Subarray  [4,3]  Is the smallest subarray in this condition .
 Copy code 

Example 2：

 Input ：target = 4, nums = [1,4,4]

 Output ：1
 Copy code 

Example 3：

 Input ：target = 11, nums = [1,1,1,1,1,1,1,1]

 Output ：0
 Copy code 

Tips ：

• 1<=target<=1091 <= target <= 10^91<=target<=109
• 1<=nums.length<=1051 <= nums.length <= 10^51<=nums.length<=105
• 1<=nums[i]<=1051 <= nums[i] <= 10^51<=nums[i]<=105

The prefix and + Two points

utilize nums[i]nums[i]nums[i] The data range of is [1,105][1, 10^5][1,105], It is known that the prefix and array satisfy 「 Monotone increasing 」.

Let's preprocess the prefix and array sum（ Prefixes and array subscripts default from 111 Start ）, For everyone nums[i]nums[i]nums[i] for , Assume that the corresponding prefix and value are s=sum[i+1]s = sum[i + 1]s=sum[i+1], We will nums[i]nums[i]nums[i] Treat as the right endpoint of the array , The question turned to ： Subscript in prefix and array [0,i][0, i][0,i] Find satisfaction in the range   Value less than or equal to s−ts - ts−t  The maximum subscript of , Serve as the previous value of the left endpoint of the array .

Using prefixes and arrays 「 Monotone increasing 」（ That is, it has two stages ）, This operation can be used 「 Two points 」 To do it .

Code ：

class Solution {
    public int minSubArrayLen(int t, int[] nums) {
        int n = nums.length, ans = n + 10;
        int[] sum = new int[n + 10];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
        for (int i = 1; i <= n; i++) {
            int s = sum[i], d = s - t;
            int l = 0, r = i;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (sum[mid] <= d) l = mid;
                else r = mid - 1;
            }
            if (sum[r] <= d) ans = Math.min(ans, i - r);
        }
        return ans == n + 10 ? 0 : ans;
    }
}
 Copy code 

• Time complexity ： The complexity of preprocessing prefix and array is O(n)O(n)O(n), The complexity of traversing prefix and array statistics answer is O(nlog⁡n)O(n\log{n})O(nlogn). The overall complexity is O(nlog⁡n)O(n\log{n})O(nlogn)
• Spatial complexity ：O(n)O(n)O(n)

Last

This is us. 「 Brush through LeetCode」 The first of the series No.209 piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .

In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates

summary

Warehouse ：github.com/SharingSour… .

In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .