hot100——11，42

283. 移动零（简单） 解法一、相向双指针 class Solution { public void moveZeroes(int[] nums) { int n = nums.length,j = 0,r = n-1; if(n == 1)return; while(nums[j] != 0)j++; for(int i = j+1;i < n;i++){ if(nums[i]!=0){ int temp = nums[j]; nums[j++] = nums[i]; nums[i] = temp; } } } }

 

11. 盛最多水的容器（中等）

解法一、相向双指针

移动较短的一支，相同时动哪里都可以。其实还可以优化，例如动过去后如果没变/变短，其实可以不更新result。

class Solution { public int maxArea(int[] height) { int n = height.length; int l = 0,r = n-1,result = Math.min(height[0],height[n-1]) * (n-1); while(l < n && r > -1 && l < r){ if(height[l] < height[r]){ l++; }else{ r--; } result = Math.max(result,Math.min(height[l],height[r]) * (r - l)); } return result; } }

以下贴出更简洁的优化

class Solution { public int maxArea(int[] height) { int i = 0, j = height.length - 1, res = 0; while(i < j) { res = height[i] < height[j] ? Math.max(res, (j - i) * height[i++]): Math.max(res, (j - i) * height[j--]); } return res; } } 作者：Krahets 链接： leetcode /problems/container-with-most-water/solutions/11491/container-with-most-water-shuang-zhi-zhen-fa-yi-do/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

15. 三数之和（中等） 解法一、相向双指针

这里有一个，在i部分跳过重复数字时，需要使用当前和上一个的判断方式，而非当前和下一个。例如，对于-1,-1,0,2这样的情况，用错误判断会导致[-1,-,1,2]被略过，即某个数字不可能出现复数次。

class Solution { public List<List<Integer>> threeSum(int[] nums) { //本质上就是二数之和 Arrays.sort(nums); int n = nums.length; List<List<Integer>> ans = new ArrayList<>(); for(int i = 0;i < n-2;i++){ // if(i+1 < n && nums[i] == nums[i+1])continue;//避免重复 if(i > 0 && nums[i] == nums[i-1])continue; if(nums[i] + nums[i+1] + nums[i+2] > 0)break; if(nums[i] + nums[n-1] + nums[n-2] < 0)continue; int j = i+1,k = n-1; while(j < k){//选开 int sum = nums[i] + nums[j] + nums[k]; if(sum == 0){//记录 List<Integer> temp = new ArrayList<>(); temp.add(nums[i]); temp.add(nums[j]); temp.add(nums[k]); ans.add(temp); j++; k--; while(j < k && nums[j] == nums[j-1]){ j++; } while(j < k && nums[k] == nums[k+1]){ k--; } }else if(sum > 0){ //大了 k--; }else{ //小了 j++; } } } return ans; } }   42. 接雨水（困难） 解法一、双数组存储法

l[i]的意思是i左侧最高的高度，r是右侧最高高度

class Solution { public int trap(int[] height) { int n = height.length; int[] l = new int[n],r = new int [n]; int lMax = 0,rMax = 0,result = 0; for(int i = 0;i < n;i++){ l[i] = lMax; lMax = Math.max(lMax,height[i]); } for(int i = n-1;i >=0;i--){ r[i] = rMax; rMax = Math.max(rMax,height[i]); } for(int i = 0;i<n;i++){ result+= Math.max(Math.min(r[i],l[i])-height[i],0); } return result; } }

解法二、相向双指针 class Solution { public int trap(int[] height) { int n = height.length; int l = 0,r = n-1,result = 0,lMax = 0,rMax=0; while(l < r){ lMax = Math.max(lMax,height[l]); rMax = Math.max(rMax,height[r]); result += lMax < rMax ? lMax- height[l++] : rMax - height[r--]; } return result; } }

解法三、单调栈 class Solution { public int trap(int[] height) { int n = height.length; int l = 0,r = n-1,result = 0,lMax = height[l],rMax = height[r]; Deque<Integer> st = new ArrayDeque<>(); for(int i = 0; i<n;i++){ //如果是空的，就加进去。如果出现的比它小，就加进去，否则弹出循环处理 while(!st.isEmpty() && height[st.peek()] <= height[i]){ int temp = st.pop(); if(!st.isEmpty())result+=(Math.min(height[st.peek()],height[i])-height[temp]) * (i - st.peek() - 1); } st.push(i); } return result; } }  

---

前段时间看完了灵神的网课和代码随想录！马上秋招了爬回来刷刷hot100，重新搭了下本地设置，感觉第一天还是有点复杂，差点忘了怎么新建数组。。