本文解决的问题: 按主题归纳 双指针、滑动窗口 相关高频题型与通用解法。
适用范围: LeetCode 中文站题目,示例主要使用 Java。
阅读建议: 先识别数据结构与不变量,再结合题目约束选择算法,不要只记忆代码。
双指针
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序(原数组的顺序)。
请注意 ,必须在不复制数组的情况下原地对数组进行操作。
**进阶:**你能尽量减少完成的操作次数吗?
提示:
1 <= nums.length <= 104
231 <= nums[i] <= 231 - 1
示例:
1 2 3 4 5
| 输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]
输入: nums = [0] 输出: [0]
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
|
public void moveZeroes(int[] nums) { if (nums == null) { return; } int j = 0; for (int i = 0; i < nums.length; ++i) { if (nums[i] != 0) { nums[j++] = nums[i]; } } for (int i = j; i < nums.length; ++i) { nums[i] = 0; } }
public void moveZeroes(int[] nums) { int l, r = 0; for (l = 0; l < nums.length; l++) { if (nums[l] != 0) { swap(nums, l, r); r++; } } } public void swap(int[] nums, int l, int r) { int temp = nums[l]; nums[l] = nums[r]; nums[r] = temp; }
|
给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
**说明:**你不能倾斜容器。
提示:
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
示例:

1 2 3 4 5 6 7
| 输入:[1,8,6,2,5,4,8,3,7] 输出:49 解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下, 容器能够容纳水(表示为蓝色部分)的最大值为 49。
输入:height = [1,1] 输出:1
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
|
public int maxArea(int[] height) { int max = 0, l = 0, r = height.length - 1; while (l < r) { int area = Math.min(height[l], height[r]) * (r - l); max = Math.max(max, area); if (height[l] < height[r]) { l++; } else { r--; } } return max; }
|
给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
**注意:**答案中不可以包含重复的三元组。
提示:
3 <= nums.length <= 3000
105 <= nums[i] <= 105
示例:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| 输入:nums = [-1,0,1,2,-1,-4] 输出:[[-1,-1,2],[-1,0,1]] 解释: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意,输出的顺序和三元组的顺序并不重要。
输入:nums = [0,1,1] 输出:[] 解释:唯一可能的三元组和不为 0 。 输入:nums = [0,0,0] 输出:[[0,0,0]] 解释:唯一可能的三元组和为 0 。
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
|
public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); Map<String, List<Integer>> map = new HashMap<>(); int l, r, k = nums.length - 1; while (k > 1) { r = k - 1; l = 0; while (l < r) { int i = nums[l] + nums[r] + nums[k]; if (i == 0) { String key = String.valueOf(nums[l]) + nums[r] + nums[k]; if (!map.containsKey(key)) { map.put(key, Arrays.asList(nums[l], nums[r], nums[k])); } r--; l++; } else if (i > 0) { r--; } else { l++; } } k--; } return new ArrayList<>(map.values()); }
public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) { if (i > 0 && nums[i] == nums[i - 1]) { continue; }
int l = i + 1, r = nums.length - 1; int target = -nums[i];
while (l < r) { int sum = nums[l] + nums[r]; if (sum == target) { res.add(Arrays.asList(nums[i], nums[l], nums[r])); l++; r--; while (l < r && nums[l] == nums[l - 1]) { l++; } while (l < r && nums[r] == nums[r + 1]) { r--; } } else if (sum < target) { l++; } else { r--; } } }
return res; }
|
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
提示:
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
示例:

1 2 3 4 5 6
| 输入:height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出:6 解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。
输入:height = [4,2,0,3,2,5] 输出:9
|
代码:解法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| public int trap(int[] height) { int n = height.length; int res = 0; int left = 0, right = n - 1; int leftMax = height[left], rightMax = height[right]; left++; right--; while(left <= right){ leftMax = Math.max(leftMax, height[left]); rightMax = Math.max(rightMax, height[right]); if(leftMax < rightMax){ res += leftMax - height[left]; left++; }else{ res += rightMax - height[right]; right--; } } return res; }
|
滑动窗口
给定一个字符串 s ,请你找出其中不含有重复字符的 最长 子串 的长度。
提示:
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
示例:
1 2 3 4 5 6 7 8 9 10 11 12
| 输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
|
public int lengthOfLongestSubstring(String s) { char[] charArray = s.toCharArray(); int res = 0; Set<Character> set = new HashSet<>(); for (int i = 0, j = 0; j < charArray.length; j++) { char c = charArray[j]; while (set.contains(c)) { set.remove(charArray[i]); i++; } set.add(c); res = Math.max(res, j - i + 1); } return res; }
|
给定两个字符串 s 和 p,找到 s ****中所有 p ****的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
提示:
1 <= s.length, p.length <= 3 * 104
s 和 p 仅包含小写字母
示例:
1 2 3 4 5 6 7 8 9 10 11 12
| 输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
输入: s = "abab", p = "ab" 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
| public List<Integer> findAnagrams(String s, String p) { List<Integer> ans = new ArrayList<Integer>(); int slen = s.length(); int plen = p.length();
if(slen<plen){ return new ArrayList<Integer>(); }
int[] count = new int[26]; for(int i=0;i<plen;i++){ count[s.charAt(i)-'a']++; count[p.charAt(i)-'a']--; }
int differ=0; for(int j=0;j<26;j++){ if(count[j]!=0){ differ++; } } if(differ==0){ ans.add(0); } for(int i=0;i<slen-plen;i++){ count[s.charAt(i)-'a']--; if(count[s.charAt(i)-'a']==0){ differ--; }else if(count[s.charAt(i)-'a']==-1){ differ++; } count[s.charAt(i+plen)-'a']++; if(count[s.charAt(i+plen)-'a']==0){ differ--; } else if(count[s.charAt(i+plen)-'a']==1){ differ++; } if(differ==0){ ans.add(i+1); } } return ans; }
|
参考资料