当前位置:网站首页>"Interview high frequency question" is 1.5/5 difficult, and the classic "prefix and + dichotomy" application question
"Interview high frequency question" is 1.5/5 difficult, and the classic "prefix and + dichotomy" application question
2022-07-02 09:07:00 【Programmer Qiqi】
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(nlogn)O(n\log{n})O(nlogn). The overall complexity is O(nlogn)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 .
边栏推荐
猜你喜欢
Shengshihaotong and Guoao (Shenzhen) new energy Co., Ltd. build the charging pile industry chain
Installing Oracle database 19C RAC on Linux
ORA-12514问题解决方法
Data type case of machine learning -- using data to distinguish men and women based on Naive Bayesian method
Hengyuan cloud_ Can aiphacode replace programmers?
Minecraft空岛服开服
kubernetes部署loki日志系统
Kubedm deploys kubernetes v1.23.5 cluster
Matplotlib剑客行——容纳百川的艺术家教程
[staff] common symbols of staff (Hualian clef | treble clef | bass clef | rest | bar line)
随机推荐
QT drag event
【Go实战基础】gin 如何绑定与使用 url 参数
Driving test Baodian and its spokesperson Huang Bo appeared together to call for safe and civilized travel
Oracle修改表空间名称以及数据文件
Cloud computing in my eyes - PAAS (platform as a service)
gocv拆分颜色通道
Talk about the secret of high performance of message queue -- zero copy technology
Qt的右键菜单
gocv opencv exit status 3221225785
commands out of sync. did you run multiple statements at once
gocv图片读取并展示
win10使用docker拉取redis镜像报错read-only file system: unknown
QT -- how to set shadow effect in QWidget
Don't spend money, spend an hour to build your own blog website
使用递归函数求解字符串的逆置问题
Pyspark de duplication dropduplicates, distinct; withColumn、lit、col; unionByName、groupBy
WSL installation, beautification, network agent and remote development
oracle修改数据库字符集
聊聊消息队列高性能的秘密——零拷贝技术
将一串数字顺序后移