双指针算法专题

前言

双指针算法入门，干就完了

下面的题目都是来自灵神的基础算法精讲，有思路不清晰的地方，可以去看讲解。

灵茶山艾府的个人空间-灵茶山艾府个人主页-哔哩哔哩视频 (bilibili.com)

相向双指针 1.两数之和

题目链接：167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）

题目描述

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1：

输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

示例 2：

输入：numbers = [2,3,4], target = 6 输出：[1,3] 解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

示例 3：

输入：numbers = [-1,0], target = -1 输出：[1,2] 解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

提示：

2 <= numbers.length <= 3 * 104-1000 <= numbers[i] <= 1000numbers 按 非递减顺序 排列-1000 <= target <= 1000仅存在一个有效答案 代码 C++ class Solution { public: vector<int> twoSum(vector<int>& numbers, int target) { int n = numbers.size(); int left = 0; int right = n - 1; while (left < right) { int s = numbers[left] + numbers[right]; if (s == target) { break; } else if (s > target) { right -= 1; } else { left += 1; } } return {left + 1, right + 1}; } }; Java class Solution { public int[] twoSum(int[] numbers, int target) { int n = numbers.length; int[] res = new int[2]; // 定义数组，用于最终答案的存储 int left = 0; int right = n - 1; while (left < right) { int s = numbers[left] + numbers[right]; if (s == target) { res[0] = left + 1; res[1] = right + 1; break; } else if (s > target) { right -= 1; } else { left += 1; } } return res; } } 2.三数之和

题目链接：15. 三数之和 - 力扣（LeetCode）

题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

示例 1：

输入：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] 。 注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。

提示：

3 <= nums.length <= 3000-105 <= nums[i] <= 105 代码 C++ class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(), nums.end()); // 对nums数组排序 vector<vector<int>> ans; // 最终结果 int n = nums.size(); // nums数组的长度 for (int i = 0; i < n - 2; i++) { // i < n - 2是要给left、right留下位置 int x = nums[i]; if (i && x == nums[i - 1]) continue; // 跳过重复数字 if (x + nums[i] + nums[i + 1] > 0) break; // 因为nums是排好序的，数组的前三个数相加都大于0了，那么后面的数字相加不可能等于0 if (x + nums[n - 1] + nums[n - 2] < 0) continue; // 如果当前的x与最大的两个数相加小于0，那么x与中间的任意数字相加都小于0，直接可以枚举下一个x了。 int left = i + 1; int right = n - 1; while (left < right) { int s = x + nums[left] + nums[right]; // 先计算出三者相加的结果 if (s > 0) right--; // s > 0的话，代表右边的数大了，所以右指针左移 else if (s < 0) left++; // s < 0的话，代表左边的数小了，所以左指针右移 else { ans.push_back({x, nums[left], nums[right]}); left++; while (left < right && nums[left] == nums[left - 1]) { // 跳过重复数字 left++; } right--; while (right > left && nums[right] == nums[right + 1]) { // 跳过重复数字 right--; } } } } return ans; } }; Java class Solution { public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); // 数组排序 List<List<Integer>> ans = new ArrayList<>(); // 最终结果 int n = nums.length; // 数组长度 for (int i = 0; i < n - 2; i++) { // 遍历数组，留出位置给左右指针 int x = nums[i]; if (i > 0 && x == nums[i - 1]) continue; // 跳过重复数字 if (x + nums[i + 1] + nums[i + 2] > 0) break; // 如果前三个数相加已经大于0，后面的数字相加不可能等于0 if (x + nums[n - 1] + nums[n - 2] < 0) continue; // 如果当前数字与最大的两个数字相加小于0，直接枚举下一个数字 int left = i + 1; int right = n - 1; while(left < right){ int s = x + nums[left] + nums[right]; if(s > 0) right--; // 右指针左移 else if(s < 0) left++; // 左指针右移 else{ ans.add(List.of(x,nums[left],nums[right])); left++; while (left < right && nums[left] == nums[left - 1]) { left++; // 跳过重复数字 } right--; while (right > left && nums[right] == nums[right + 1]) { right--; // 跳过重复数字 } } } } return ans; } } 3.最接近的三数之和

题目链接：16. 最接近的三数之和 - 力扣（LeetCode）

题目描述

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1：

输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

示例 2：

输入：nums = [0,0,0], target = 1 输出：0

提示：

3 <= nums.length <= 1000-1000 <= nums[i] <= 1000-104 <= target <= 104

优化来自灵神，不得不说，灵神yyds，下面为灵神的题解

16. 最接近的三数之和 - 力扣（LeetCode）

代码 C++ class Solution { public: int threeSumClosest(vector<int>& nums, int target) { sort(nums.begin(),nums.end()); int n = nums.size(); int minDiff = INT_MAX; int ans = 0; for (int i = 0; i < n - 2; i++) { int x = nums[i]; // 优化三 if(i > 0 && x == nums[i - 1]){ continue; } // 优化一 int res = x + nums[i+1] + nums[i+2]; if(res > target){ // 后面无论怎么选，选出的三个数的和不会比res小 if(res - target < minDiff){ ans = res; } break; } // 优化二 res = x + nums[n - 1] + nums[n - 2]; if(res < target){ // x 加上后面任意两个数都不超过 s，所以下面的双指针就不需要跑了 if(target - res < minDiff){ minDiff = target - res; ans = res; } continue; } // 双指针 int left = i + 1, right = n - 1; while (left < right) { int res = x + nums[left] + nums[right]; if (res == target) { return target; } else if (res < target) { if (target - res < minDiff) { // 找到更接近 target 的数 minDiff = target - res; ans = res; } left++; } else {// res > target if (res - target < minDiff) { // 找到更接近 target 的数 minDiff = res - target; ans = res; } right--; } } } return ans; } }; Java class Solution { public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int n = nums.length; int minDiff = Integer.MAX_VALUE; int ans = 0; for (int i = 0; i < n - 2; i++) { int x = nums[i]; // 优化三 if (i > 0 && x == nums[i - 1]) { continue; } // 优化一 int res = x + nums[i + 1] + nums[i + 2]; if (res > target) { // 后面无论怎么选，选出的三个数的和不会比res小 if (res - target < minDiff) { ans = res; } break; } // 优化二 res = x + nums[n - 1] + nums[n - 2]; if (res < target) { // x 加上后面任意两个数都不超过 s，所以下面的双指针就不需要跑了 if (target - res < minDiff) { minDiff = target - res; ans = res; } continue; } // 双指针 int left = i + 1, right = n - 1; while (left < right) { res = x + nums[left] + nums[right]; if (res == target) { return target; } else if (res < target) { if (target - res < minDiff) { // 找到更接近 target 的数 minDiff = target - res; ans = res; } left++; } else { // res > target if (res - target < minDiff) { // 找到更接近 target 的数 minDiff = res - target; ans = res; } right--; } } } return ans; } } 4.盛最多水的容器

题目链接：11. 盛最多水的容器 - 力扣（LeetCode）

题目描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

**说明：**你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1] 输出：1

提示：

n == height.length2 <= n <= 1050 <= height[i] <= 104 代码 C++ class Solution { public: int maxArea(vector<int>& height) { int n = height.size(); int left = 0; int right = n - 1; int res = 0,area = 0; while(left < right){ area = (right - left) * min(height[left],height[right]); res = max(res,area); if(height[left] < height[right]){ left++; } else { right--; } } return res; } }; Java class Solution { public int maxArea(int[] height) { int n = height.length; int left = 0; int right = n - 1; int res = 0; while(left < right){ int area = Math.min(height[left],height[right]) * (right - left); res = Math.max(res,area); if(height[left] < height[right]){ left++; }else{ right--; } } return res; } } 5.接雨水

题目链接：42. 接雨水 - 力扣（LeetCode）

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：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 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5] 输出：9

提示：

n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105 代码 C++ class Solution { public: int trap(vector<int>& height) { int n = height.size(); int left = 0, right = n - 1; int pre_max = 0, suf_max = 0; int ans = 0; while (left < right) { pre_max = max(pre_max, height[left]); // 更新前缀最大值 suf_max = max(suf_max, height[right]); // 更新后缀最大值 if (pre_max < suf_max) { // 柱子雨水高度是该柱子前后缀最高柱子的较小者 ans += pre_max - height[left]; // 当前位置雨水高度减去柱子高度 left++; // 左指针右移 } else { ans += suf_max - height[right]; // 当前位置雨水高度减去柱子高度 right--; // 右指针左移 } } return ans; } }; Java class Solution { public int trap(int[] height) { int n = height.length; int left = 0, right = n - 1; int pre_max = 0, suf_max = 0; int ans = 0; while (left < right) { pre_max = Math.max(pre_max, height[left]); // 更新前缀最大值 suf_max = Math.max(suf_max, height[right]); // 更新后缀最大值 if (pre_max < suf_max) { // 柱子雨水高度是该柱子前后缀最高柱子的较小者 ans += pre_max - height[left]; // 当前位置雨水高度减去柱子高度 left++; // 左指针右移 } else { ans += suf_max - height[right]; // 当前位置雨水高度减去柱子高度 right--; // 右指针左移 } } return ans; } } 同向双指针(滑动窗口) 1.长度最小的子数组

题目链接：209. 长度最小的子数组 - 力扣（LeetCode）

题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4] 输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1] 输出：0

提示：

1 <= target <= 1091 <= nums.length <= 1051 <= nums[i] <= 105 思路

滑动窗口

代码 C++ class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int n = nums.size(); int ans = n + 1; int left = 0, s = 0; for (int right = 0; right < n; right++) { s += nums[right]; while (s >= target) { ans = min(ans, right - left + 1); s -= nums[left]; left++; } } return ans <= n ? ans : 0; } }; Java class Solution { public int minSubArrayLen(int target, int[] nums) { int n = nums.length; int ans = n+1; int left = 0, s = 0; for(int right = 0;right < n; right++){ s += nums[right]; while(s >= target){ ans = Math.min(ans, right - left +1); s -= nums[left]; left++; } } return ans <= n ? ans : 0; } } 2.乘积小于K的子数组

题目链接：713. 乘积小于 K 的子数组 - 力扣（LeetCode）

题目描述

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

示例 1：

输入：nums = [10,5,2,6], k = 100 输出：8 解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。 需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。

示例 2：

输入：nums = [1,2,3], k = 0 输出：0

提示:

1 <= nums.length <= 3 * 1041 <= nums[i] <= 10000 <= k <= 106 思路

滑动窗口

代码 C++ class Solution { public: int numSubarrayProductLessThanK(vector<int>& nums, int k) { int n = nums.size(); int ans = 0; // 结果 int left = 0; int s = 1; if(k <= 1){ return 0; } for(int right = 0; right < n; right++){ s *= nums[right]; while( s >= k){ s /= nums[left]; left++; } ans += right - left + 1; } return ans; } }; Java class Solution { public int numSubarrayProductLessThanK(int[] nums, int k) { int n = nums.length; int ans = 0; int s = 1; int left = 0; if(k <= 1){ return 0; } for(int right = 0;right < n; right++){ s *= nums[right]; while(s >= k){ s /= nums[left]; left++; } ans += right - left + 1; } return ans; } } 3.无重复字符的最长子串

题目链接：3. 无重复字符的最长子串 - 力扣（LeetCode）

题目描述

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

0 <= s.length <= 5 * 104s 由英文字母、数字、符号和空格组成 思路

滑动窗口

代码 C++ class Solution { public: int lengthOfLongestSubstring(string s) { int n = s.length(); int ans = 0, left = 0; unordered_set<char> window; // 维护当前子串的字符集合 for (int right = 0; right < n; right++) { char c = s[right]; while (window.count(c)) { window.erase(s[left]); left++; } window.insert(c); ans = max(ans, right - left + 1); } return ans; } }; Java class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(); int ans = 0, left = 0; HashSet<Character> window = new HashSet<>(); for (int right = 0; right < n; right++) { char c = s.charAt(right); while (window.contains(c)) { // 判断是否重复 window.remove(s.charAt(left)); left++; } window.add(c); ans = Math.max(ans, right - left + 1); } return ans; } }