【LeetCode-经典面试150题-day8】

11.盛最多水的容器

题意：

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

【输入样例】

[1,8,6,2,5,4,8,3,7]

【输出样例】49

解题思路：转换成求长方形的最大面积

1.双指针i,j分别指向数组的头和尾，i和j之间的距离为长方形的长

2. 长方形的高为min(height[i],height[j]),

3.定义一个变量来存储能找到的最大面积

开干

class Solution {public int maxArea(int[] height) {int i = 0,j = height.length - 1;int maxWater = 0;while(i<j){//i不能等于j，等于j只是一条垂线，没有面积，没有办法盛水maxWater = Math.max(maxWater,(j-i)* Math.min(height[i],height[j]));if(height[i] < height[j]){//当左边比右边小时，左指针i往右走，看在减少长度的时候，能不能增加高度++i;}else{--j;}}return maxWater;}
}

时间：击败了59.09%

内存：击败了16.11%

15.三数之和

题意：

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

【输入样例】

nums=[-1,0,1,2,-1,-4]

【输出样例】[[-1,-1,2],[-1,0,1]]

解题思路：排序+双指针

1.先将数组进行排序（升序）（注意，下文a,b,c值的是下标）

2.枚举a，定下a后，从剩余数组中确定b(a+1)和c(nums.length-1),判断三者相加跟0之间的关系，如果相等，则填入此三元组到result中；如果小于0，则b++，往右移动寻找较大只；如果三者相加大于0，减小c。内部b和c的循环终止条件是b>=c，而不是说a+b+c=0,因为可能有多个取值，比如nums[a]为-3，nums[b]，nums[c]可以是-2和5，也可以是-1和4；

3.a继续往后枚举，直到nums[a]本身就大于0，循环结束

4.题目要求不能包含重复的三元组，确定a时，需要判断nums[a-1]的值是否与nums[a]相等，相等不能再使用，继续遍历，b和c也是一样。

class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);int a,b,c;List<List<Integer>> result = new ArrayList<>();for(a=0;a<nums.length;a++){if(nums[a] > 0) break;if(a > 0 && nums[a] == nums[a-1]) continue;//继续寻找下一个ab = a+1;c = nums.length-1;while(b < c){int sum = nums[a]+nums[b]+nums[c];if( sum < 0){++b;}else if(sum > 0){--c;}else{List<Integer> r1 = Arrays.asList(nums[a], nums[b], nums[c]);result.add(r1);while(b < c && nums[b] == nums[b+1]) ++b;while(b < c && nums[c] == nums[c-1]) --c;++b;--c;}}}return result;}
}

时间：击败了91.31%

内存：击败了64.32%

209.长度最小的子数组

题意：

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

【输入样例】

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

【输出样例】2

解题思路：

暴力枚举，注意题目中的要求，是大于等于target，并且是连续的子数组

暴力枚举会超时，仅学习参考

class Solution {public int minSubArrayLen(int target, int[] nums) {//注意求的是大于等于target,并且是一段连续的子数组int result = nums.length + 1;int sum = 0;//子序列的数值之和int subLength = 0;//子序列的长度for(int i=0;i<nums.length;++i){//子序列开始sum = 0;for(int j = i;j<nums.length;++j){//子序列结束sum += nums[j];if(sum >= target){//更新结果subLength = j-i+1;result = result < subLength ? result : subLength;break;//从下一个i继续找}}}return result == nums.length + 1 ? 0: result;}
}

解题思路：

利用双指针实现滑动窗口解法

1.指针j指向窗口的结束位置

2.指针i指向窗口的起始位置

3.枚举j的位置，并不断累加，当sum大于等于target时，可以尝试将i往右挪动时，得到的结果是否仍然大于target，注意，i++之前，sum-=nums[i]是必要的，因为往右一步后，窗口里面的总和不包括nums[i].

4. 窗口滑动过程中，不断判断当前满足条件的长度与result相比那个小。

class Solution {public int minSubArrayLen(int target, int[] nums) {//滑动窗口//指针i指向窗口的左边，指针j指向窗口的右边//根据窗口的和值是否大于target来判断是否要移动窗口看int result = nums.length + 1;int sum = 0;//子序列的数值之和int subLength = 0;//子序列的长度int i =0;//默认每次窗口的其实位置都是第一位for(int j=0;j<nums.length;++j){//子序列开始sum += nums[j];while(sum >= target){//当加起来的值大于目标值之后，可以判断此时i能不能往前滑动subLength = j-i+1;result = result < subLength ? result : subLength;sum -= nums[i];++i;//判断i往右滑动一步之后，是否还能符合条件，不能的话，内层while结束，外层j继续滑动}}return result == nums.length + 1 ? 0: result;}
}

时间：击败了99.69%

内存：击败了57.73%

3.无重复字符的最长字串

题意：

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

【输入样例】

s="abcabcbb"

【输出样例】3

解题思路：

因为经典面试150题给它归纳在滑动窗口里面，而上一道题209是我做的第一道滑动窗口题，所以立马就猜到了用滑动窗口实现。

不重复字符，考虑用map，将字符作为key

class Solution {public int lengthOfLongestSubstring(String s) {if(s.length()==0){return 0;}int i=0;int subLength = 0;int result = 0;Map<Character,Integer> map = new HashMap<>();for(int j=0;j<s.length();++j){char c = s.charAt(j);while(map.containsKey(c)){//如果map已经有这个字符了，左指针往右挪一步//挪动前需要先删掉map.remove(s.charAt(i));++i;}map.put(c,j);result = Math.max(result,j-i+1);}return result;}
}