双指针| Java | (hot100) 力扣283, 11, 15, 42做题总结
leetcode 11 盛最多水的容器
双层for循环暴力
- 超出时间限制
class Solution {public int maxArea(int[] height) {int h=0;int v=0;for(int i=0; i<height.length; i++) {for(int j=i+1; j<height.length; j++) {h = Math.min(height[i],height[j]);v = Math.max(v, h*(j-i));}}return v;}
}
双指针
设两指针 i , j ，指向的水槽板高度分别为 h[i] , h[j] ，此状态下水槽面积为 S(i,j) 。由于可容纳水的高度由两板中的 短板 决定，因此可得如下 面积公式 S(i,j)=min(h[i],h[j])×(j−i)
在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽 底边宽度 −1 变短：
若向内 移动短板 ，水槽的短板 min(h[i],h[j]) 可能变大，因此下个水槽的面积 可能增大 。
若向内 移动长板 ，水槽的短板 min(h[i],h[j]) 不变或变小，因此下个水槽的面积 一定变小 。
class Solution {public int maxArea(int[] height) {int i=0,j=height.length-1;int res=0;while(i<j) {//体积res = Math.max(res, Math.min(height[i],height[j])*(j-i));if(height[i] < height[j]) {i++;} else {j--;}}return res;}
}
leetcode 283 移动零
- 双指针
第三次了，终于一次做对
class Solution {public void moveZeroes(int[] nums) {int x=0;for(int i=0; i<nums.length; i++) {if(nums[i] != 0) {nums[x++] = nums[i];}}for(int i=x; i<nums.length; i++) {nums[i] = 0;}}
}
leetcode 15 三数之和
- 不记得思路了！！其实本质还是3层for循环，然后用双指针降低时间复杂度。
出错点
① 必须要写 left<right，因为后面nums[left] nums[right]会边界溢出
② left++ right–必须要加
class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> ans = new ArrayList<>();Arrays.sort(nums);int left,right,sum;for(int i=0; i<nums.length; i++) {if(nums[i] > 0) return ans;if(i>0 && nums[i] == nums[i-1]) continue;left = i+1;right = nums.length-1;while(left < right) {sum = nums[i]+nums[left]+nums[right];if(sum > 0) {right--;} else if(sum < 0) {left++;} else {List<Integer> list = new ArrayList<Integer>();list.add(nums[i]);list.add(nums[left]);list.add(nums[right]);ans.add(list);// ans.add(Arrays.asList(nums[i], nums[left], nums[right]));// 去重逻辑应该放在找到一个三元组之后，对b 和 c去重//去重while(left<right && nums[left+1]==nums[left]) left++;while(left<right && nums[right-1]==nums[right]) right--;left++;right--;}}}return ans;}
}
二数之和
class Solution {public int[] twoSum(int[] nums, int target) {HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();int[] ans = new int[2];for(int i=0; i<nums.length; i++) {if(map.containsKey(target-nums[i])) {ans[0] = map.get(target-nums[i]);ans[1] = i;break;}map.put(nums[i], i);}return ans;}
}
四数之和
- 和三数之和差不多，但忘记怎么写了
class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> res = new ArrayList<>();Arrays.sort(nums);int left=0,right=0;long sum=0;for(int i=0; i<nums.length; i++) {//i去重if(i>0 && nums[i]==nums[i-1]) continue;for(int j=i+1; j<nums.length; j++) {if(j>(i+1) && nums[j]==nums[j-1]) continue;left=j+1;right=nums.length-1;while(left<right) {sum = (long)nums[i]+nums[j]+nums[left]+nums[right];if(sum > target) {right--;} else if(sum < target) {left++;} else {List<Integer> list = new ArrayList<>();list.add(nums[i]);list.add(nums[j]);list.add(nums[left]);list.add(nums[right]);res.add(list);// left right 去重while(left<right && nums[left+1]==nums[left]) left++;while(left<right && nums[right-1]==nums[right]) right--;left++;right--;}}}}return res;}
}
leetcode 42 接雨水
- zhe