算法题目总结-双指针

1.滑动窗口类型

1.长度最小的子数组

1.答案

package com.sunxiansheng.arithmetic.day10;/*** Description: 209. 长度最小的子数组** @Author sun* @Create 2025/1/15 10:53* @Version 1.0*/
public class t209 {public static int minSubArrayLen(int target, int[] nums) {// 窗口定义：窗口内的元素要小于targetint left = 0;int sum = 0;// 记录结果int res = Integer.MAX_VALUE;for (int right = 0; right < nums.length; right++) {// 求和sum += nums[right];// 当窗口不满足要求时，记录结果，移动左指针while (sum >= target) {res = Math.min(res, right - left + 1);sum -= nums[left];left++;}}return res == Integer.MAX_VALUE ? 0 : res;}
}

2.思路

窗口定义：窗口内的元素要小于target，当窗口不满足要求时，记录结果，移动左指针

2.无重复字符的最长子串

1.答案

package com.sunxiansheng.arithmetic.day10;import java.util.HashSet;
import java.util.Set;/*** Description: 3. 无重复字符的最长子串** @Author sun* @Create 2025/1/15 11:01* @Version 1.0*/
public class t3 {public static int lengthOfLongestSubstring(String s) {// 窗口定义：窗口内的元素不能重复int left = 0;// 窗口Set<Character> set = new HashSet<>();// 结果int res = 0;for (int right = 0; right < s.length(); right++) {// 判断是否重复boolean flag = set.contains(s.charAt(right));// 加入窗口set.add(s.charAt(right));// 计算结果res = Math.max(res, set.size());// 如果重复了if (flag) {// 只要左指针指向的元素不等于右指针指向的元素，就一直移动左指针while (s.charAt(left) != s.charAt(right)) {set.remove(s.charAt(left));left++;}// 到这里说明左指针指向了重复元素，再移动一次left ++;}}return res;}
}

2.思路

窗口定义：窗口内的元素不能重复，先判断一下是否重复了，然后加入窗口，计算结果，如果真的重复了，就一直滑动窗口，直到将重复的元素移除

2.双指针类型

1.盛最多水的容器

1.答案

package com.sunxiansheng.arithmetic.day11;/*** Description: 11. 盛最多水的容器** @Author sun* @Create 2025/1/16 09:57* @Version 1.0*/
public class t11 {public static int maxArea(int[] height) {int max = 0;// 双指针int left = 0, right = height.length - 1;while (left < right) {// 求水量max = Math.max(max, Math.min(height[left], height[right]) * (right - left));// 如果左边小于右边，左指针移动if (height[left] < height[right]) {left++;} else {// 其余情况，右指针向左移动right--;}}return max;}
}

2.思路

就是用两个指针指向两边，先求水量和最大值，然后哪边指针的height低就移动哪边的指针

2.三数之和

1.答案

package com.sunxiansheng.arithmetic.day11;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;/*** Description: 15. 三数之和** @Author sun* @Create 2025/1/16 10:02* @Version 1.0*/
public class t15 {public static List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> res = new ArrayList<>();// 先排序Arrays.sort(nums);// 一层遍历 + 双指针for (int i = 0; i < nums.length - 2; i++) {// 1.当前元素跟前一个元素相同时不考虑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) {res.add(Arrays.asList(nums[i], nums[left], nums[right]));// 2.左右指针指向的下一个元素跟当前元素相同也不考虑while (left < right && nums[left] == nums[left + 1]) {left++;}while (left < right && nums[right] == nums[right - 1]) {right--;}left++;right--;} else if (sum < 0) {left++;} else {right--;}}}return res;}
}

2.思路

一次遍历加上双指针，然后有两个去重点，一个是遍历遇到相同元素时的去重，另一个是左右指针遇到相同元素的去重】