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;//继续寻找下一个a
b = 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;
}
}时间： 击败了20.12%
内存： 击败了41.36%
