leetcodeHot100(3、4、5)

如有错误欢迎指正3、最长连续序列128. 最长连续序列 - 力扣LeetCodeclassSolution{publicintlongestConsecutive(int[]nums){HashSetIntegersetnewHashSet();IntegerMax0;//放入set容器for(Integernum:nums){set.add(num);}//剪枝查询for(Integernum:set){if(set.contains(num-1)){continue;}Integerinum;while(set.contains(i1)){i;}MaxMath.max(Max,(i-num1));}returnMax;}}首先题目要求O(n) 的算法解决此问题放弃排序使用 HashSet 实现 O(1) 查询将数组去重后存储。可以把数据放入set中进行操作操作时间复杂度就降到最低在set中我们暴力遍历找每个位置上的数是否有相邻值一定超时可能退化为 O(n²)采用剪枝优化遍历每个元素时通过判断 num - 1 是否存在来确定是否为连续序列起点仅从起点向右扩展序列避免重复计算使整体时间复杂度降低至 O(n)4、移动零283. 移动零 - 力扣LeetCodeclassSolution{publicvoidmoveZeroes(int[]nums){//最后一个0的位置Integerlow00;for(inti0;inums.length;i){if(nums[i]!0){Integertempnums[i];nums[i]nums[low0];nums[low0]temp;low0;}}}}左指针为当前应该放置非0元素的位置右指针用于遍历数组寻找非0元素当右指针遇到非0时将其与左指针位置交换使非0元素向前移动0被挤到后面交换后左指针右移右指针继续向后遍历直到数组遍历完成后面全是05、盛最多的水11. 盛最多水的容器 - 力扣LeetCodeclassSolution{publicintmaxArea(int[]height){Integerans0,left0,rightheight.length-1;while(leftright){IntegerareaMath.min(height[left],height[right])*(right-left);ansMath.max(ans,area);if(height[left]height[right]){left;}else{right--;}}returnans;}}题目的容器由两条边组成适合使用左右双指针根据短板效应容器的高度由较短的一边决定面积 底 × 高每次计算当前左右指针形成的面积并不断更新最大值移动策略只移动较短的一侧指针假设当前左右高度为 h_left 和 h_right且 h_left h_right若移动右指针较长的一侧宽度变小高仍受 h_left 限制面积一定变小或不变若移动左指针较短的一侧有可能遇到更高的柱子使高度提升从而有机会得到更大的面积因此为了不遗漏最优解应始终移动较短的一侧