双指针题总结

hot100

移动零

题目链接：
283.移动零
代码：

class Solution {public void moveZeroes(int[] nums) {int slow = 0;for (int fast = 0; fast < nums.length; fast ++){if (nums[fast] != 0){nums[slow++] = nums[fast];}}for (int i = slow; i < nums.length; i ++){nums[i] = 0;}}
}

盛水最多的容器

题目链接：
11.盛水最多的容器
代码：

class Solution {public int maxArea(int[] height) {int res = 0;int left = 0, right = height.length - 1;while (left < right) {if (height[left] < height[right]) {res = Math.max(res, (right - left)*height[left]);left ++;}else {res = Math.max(res, (right - left)*height[right]);right --;}}return res;}
}

三数之和

题目链接：
15.三数之和
代码：

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> res = new ArrayList<>();Arrays.sort(nums);for (int i = 0; i < nums.length; i ++){if (nums[i] > 0) {return res;}if (i > 0 && nums[i] == nums[i - 1]) {continue;}int left = i + 1;int right = nums.length - 1;while (left < right) {int sum = nums[i] + nums[left] + nums[right];if (sum > 0) {right --;} else if (sum < 0) {left ++;} else {res.add(Arrays.asList(nums[i], nums[left], nums[right]));while (left < right && nums[right] == nums[right - 1]) {right --;}while (left < right && nums[left] == nums[left + 1]) {left ++;}right --;left ++;}}}return res;}
}

接雨水

题目链接：
42.接雨水
代码：

class Solution {public int trap(int[] height) {int res = 0;int left = 0, right = height.length - 1;int maxLeft = 0, maxRight = 0;while (left < right) {maxLeft = Math.max(maxLeft, height[left]);maxRight = Math.max(maxRight, height[right]);if (height[left] < height[right]) {res += maxLeft - height[left];left ++;} else {res += maxRight - height[right];right --;}}return res;}
}

最小覆盖子串

题目链接：
76.最小覆盖子串
代码：

class Solution {public String minWindow(String s, String t) {Map<Character, Integer> need = new HashMap<>();Map<Character, Integer> has = new HashMap<>();int left = 0, right = 0;int valid = 0;int start = 0, minLen = Integer.MAX_VALUE;for (char c : t.toCharArray()) need.put(c,need.getOrDefault(c,0) + 1);while(right < s.length()){char r = s.charAt(right);right ++;if (need.containsKey(r)){has.put(r,has.getOrDefault(r,0) + 1);if (has.get(r).equals(need.get(r))) valid ++;}while (valid == need.size()){if (right - left < minLen){start = left;minLen = right - left;}char l = s.charAt(left);if (need.containsKey(l)){has.put(l,has.get(l) - 1);if (has.get(l) < need.get(l)) valid --;}left ++;}}return minLen == Integer.MAX_VALUE ? "" : s.substring(start,start + minLen);}
}