LeetCode Hot100刷题指南(第一期)
大家好 我是寸铁
临近秋招,让我们一起刷题吧
每期5道题 持续更新中 
欢迎点赞 + 关注 
往期回顾
蓝桥杯上岸全指南
283. 移动零
双指针算法:
left
用于维护左端点,right
用于维护右端点。
left
的移动随着right
的移动而移动
要将非0的数字按照顺序排好
从左往右,扫描整个区间。
left
记录的是当前0的位置。
right
记录的是当前的非0数的位置
遇到非0的数字直接和left
指向的位置交换即可
这样可以实现将整个区间为0的数字移动到数组末端
Accode
class Solution {
public void moveZeroes(int[] nums) {
int left = 0;
int right = 0;
for(int i = 0; i<nums.length; i++){
if(nums[i] != 0){
swap(nums,left,right);
left++;
}
right++;
}
}
public void swap(int nums[],int left,int right){
int temp = nums[right];
nums[right] = nums[left];
nums[left] = temp;
}
}
3.无重复字符的最长子串
双指针算法+滑动窗口:
处理此类题无外乎两种思路:
1.以某个字母为开始的子串
2.以某个字母为结尾的子串
这里按照顺序习惯,选择以字母开始的思路
便于枚举,更加直观。
依次枚举每个字母为开头的序列
需要用到HashSet
维护好这段区间,也就是滑动窗口。
怎么维护?
当我的哈希表中不包含该字母时,将该字母加入哈希表。
直至最后枚举时,哈希表中遇到重复的字符停止扫描。
再计算当前窗口的长度大小
最后取枚举以区间每个字符为开始的字符的子串的最大值即可。
注意
这里的ans
要取0
不能取负数
为什么?
因为字符可以为空即" "
时间复杂度
枚举一轮n
次,每轮枚举最多n
次
总计:O(n^2)
Accode
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character>set = new HashSet<Character>();
int len = s.length();
int r = -1 , ans = 0;
for (int i = 0; i < len; i++){
if(i != 0){
set.remove(s.charAt(i - 1));
}
while(r + 1 < len && !set.contains(s.charAt(r + 1))){
set.add(s.charAt( r + 1));
r++;
}
ans = Math.max(ans,r - i + 1);
}
return ans;
}
}
15. 三数之和
ACcode
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
Arrays.sort(nums);
int n = nums.length;
for (int i = 0; i < n; i++){
if (i>0 && nums[i] == nums[i-1]){
continue;
}
int res = - nums[i];
int k = n-1;
for (int j = i + 1; j < n; j++){
if( j > i + 1 && nums[j] == nums[j-1] ){
continue;
}
while( j < k && nums[k] + nums[j] > res){
k--;
}
if(k == j){
break;
}
if(nums[k] + nums[j] == res){
List<Integer> list = new ArrayList<Integer>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[k]);
ans.add(list);
}
}
}
return ans;
}
}
128. 最长连续序列
题目描述:
给定一个未排序的整数数组 nums
,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
O(n):最多只有一重for循环
这道题一重for循环实现足矣!!!
下面分为两大类去讨论:
第一类:
当数组内容为空或者数组长度为0时,返回0即可
第二类:
当数组内容为空或者数组长度不为0时
题目要求的是连续序列,即1、2、3、4、...、n+1
相邻元素之差必定为1,则为连续序列。
那我们可以先对整个数组排个序
- 相邻元素之差为1
即nums[i] - nums[i-1]==1
满足条件,则sum++
。
更新连续序列的长度加1
注意
注意sum初始值为1
为什么?举个例子
`1 2 3`
连续序列长度为3
如果sum=0,更新两次则sum++两次最后为2
sum = 1,他自己本身也是序列的一部分。
并且,数组非空,最差情况下也有1个数
如:1 5 5 5 5
序列长度为1 而不是0
- 相邻元素之差为0
像 1 2 3 4 5 5 5 5 5 … 这类数列
最大长度为5,遇到重复元素直接continue
- 相邻元素之差大于1
这也是为什么需要引入lastsum变量
lastsum:表示的是上一个满足条件的序列长度
或者说是以第i
个数为结尾的连续序列长度
这也是为什么for循环从1
开始枚举,而不是从0
开始。
sum:表示的是当前满足条件的序列长度
当相邻元素之差大于1时,说明已经和前面的连续序列断开连续了。
需要将原先sum的值重置为1。
重置完后,再继续往下走,看有无满足条件的数字出现,有则更新序列的长度。
即max(sum , lastsum);
class Solution {
public int longestConsecutive(int[] nums) {
if(nums.length == 0|| nums == null)return 0;
Arrays.sort(nums);
int sum = 1;
int lastsum = sum;//当前的最大长度为sum
for(int i = 1; i < nums.length; i++){
if(nums[i] - nums[i-1] == 1){
sum++;//找到满足条件的sum++
lastsum = Math.max(sum , lastsum);//更新当前的sum和上次的sum的最大值
}
else if(nums[i] == nums[i-1]){
continue;//相等元素直接跳过
}
else{
//nums[i] - nums[i-1] > 1
//此时则不连续,将sum重新置为1
//看往下走能不能找到连续的序列
//更新和上次的lastsum的最大值
sum = 1;
}
}
return lastsum;
}
}
560. 和为 K 的子数组
思路
- 先对数组中的所有数字求一遍前缀和
- 得到以每个数字结尾的前缀和
- 再用两重
for
循环,用当前数字的前缀和依次减去前面数字的前缀和 - 存在差值为
k
,则得到和为k
的连续子数组。
模拟
nums[]:1,1,1
p[0] = 0;
p[1] = 1 + p[0] = 1 + 0 = 1;
p[2] = 1 + p[1] = 1 + 1 = 2;
p[3] = 1 + p[2] = 1 + 2 = 3;
这里得到:
p[3] - p[2] = k = 2;
p[2] - p[0] = k = 2;
注意:
由于数组下标从0
开始,求nums[0]
的前缀和等于p[1]
nums[0]
的前缀和等于 0 + nums[0] = 0 + 1 = p[0] + 1 = 1 = p[1]
数组需要多开1个单位,保险起见,索性开多10个单位
为什么是对的?
当前数字的前缀和减去前面数字的前缀和等于k
说明这中间存在若干个数的和值为k
假设p[2] = 3;
p[6] = k + 3;
p[6] - p[2] = k;
可以发现:某个数的前缀和包含了前面某个数的前缀和
减去后相当于得到一段左开右闭区间的若干个数的和值
再验证是否为k
即可。
ACcode
class Solution {
public int subarraySum(int[] nums, int k) {
int len = nums.length;
int []p = new int [len+10];
p[0] = 0;//精华
for(int i = 0; i < len; i++){
p[i + 1] = p[i] + nums[i];
}
int sum = 0;
for(int i = 0; i < len; i++){
for(int j = i; j < len; j++){
if(p[j + 1] - p[i] == k){
sum++;
}
}
}
return sum;
}
}
☀️☀️☀️☀️☀️☀️
后续有补充,持续更新中🌋
喜欢的伙伴点点赞,关个注💗