https://leetcode-cn.com/tag/two-pointers/
题目汇总
350. 两个数组的交集 II简单[✔]
424. 替换后的最长重复字符中等（？？？）
457. 环形数组循环中等（？？？）
524. 通过删除字母匹配到字典里最长单词中等
532. 数组中的K-diff数对简单[✔]
567. 字符串的排列中等（？？）
632. 最小区间困难（？？？）
713. 乘积小于K的子数组中等（？？）
350. 两个数组的交集 II简单
给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]
说明：
输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。
进阶:
如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小很多，哪种方法更优？
如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办?
与 349. 两个数组的交集简单的区别在于输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
思路：排序预处理+双指针
将两个数组排序，设置两个指针，分别从每个数组的第一个元素开始比较，移动指针，相等元素存入List中，将list的元素写入一个新的数组中，并输出。
class Solution {//执行用时 :3 ms, 在所有 Java 提交中击败了88.45%的用户
public int[] intersect(int[] nums1, int[] nums2) {
if(nums1 == null || nums1.length < 0 || nums2 == null || nums2.length < 0)
return new int[0];
Arrays.sort(nums1);
Arrays.sort(nums2);
List<Integer> list = new ArrayList<>();
int i = 0;
int j = 0;
while(i < nums1.length && j < nums2.length){
if(nums1[i] == nums2[j]){
list.add(nums1[i]);
i++;
j++;
}else if(nums1[i] < nums2[j]){
i++;
}else{
j++;
}
}
//将list的元素写入一个新的数组中
int[] res = new int[list.size()];
int index = 0;
for(int num:list){
res[index] = num;
index++;
}
return res;
}
}
424. 替换后的最长重复字符中等
给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k次。在执行上述操作后，找到包含重复字母的最长子串的长度。
注意:
字符串长度 和 k 不会超过 104。
示例 1:
输入:
s = "ABAB", k = 2
输出:4
解释:
用两个'A'替换为两个'B',反之亦然。
示例 2:
输入:
s = "AABABBA", k = 1
输出:4
解释:
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。
思路：双指针滑动窗口
class Solution {//执行用时 :6 ms, 在所有 Java 提交中击败了70.64%的用户
int[] count = new int[26];//当前窗口中各个字母的出现次数
public int characterReplacement(String s, int k) {
int len = s.length();
if(s == null || len < 1)
return 0;
char[] chars = s.toCharArray(); //将字符串对象中的字符转换为一个字符数组
int left = 0;
int charMax = 0;//滑动窗口内相同字母出现次数的历史最大值
int res = 0;
for(int right=0;right<len;right++){
int index = chars[right] - 'A';
count[index]++;
charMax = Math.max(charMax, count[index]);// 比较之前记录的最大数 和 当前字符的数量
if (right - left + 1 - charMax > k) {//当前需要替换的字符数大于k
count[chars[left] - 'A']--;// 将窗口最左边的字符 在计数数组中减1
left++;// 滑动窗口
}
res = Math.max(res, right-left+1);
}
return res;
}
}
457. 环形数组循环中等
给定一个含有正整数和负整数的环形数组
nums。 如果某个索引中的数 k 为正数，则向前移动 k 个索引。相反，如果是负数 (-k)，则向后移动 k 个索引。因为数组是环形的，所以可以假设最后一个元素的下一个元素是第一个元素，而第一个元素的前一个元素是最后一个元素。
确定nums中是否存在循环（或周期）。循环必须在相同的索引处开始和结束并且循环长度 > 1。此外，一个循环中的所有运动都必须沿着同一方向进行。换句话说，一个循环中不能同时包括向前的运动和向后的运动。
示例 1：
输入：[2,-1,1,2,2]
输出：true
解释：存在循环，按索引 0 -> 2 -> 3 -> 0 。循环长度为 3 。
示例 2：
输入：[-1,2]
输出：false
解释：按索引 1 -> 1 -> 1 ... 的运动无法构成循环，因为循环的长度为 1 。根据定义，循环的长度必须大于 1 。
示例 3:
输入：[-2,1,-1,-2,-2]
输出：false
解释：按索引 1 -> 2 -> 1 -> ... 的运动无法构成循环，因为按索引 1 -> 2 的运动是向前的运动，而按索引 2 -> 1 的运动是向后的运动。一个循环中的所有运动都必须沿着同一方向进行。
提示：
- -1000 ≤ nums[i] ≤ 1000
- nums[i] ≠ 0
- 0 ≤ nums.length ≤ 5000
进阶：
你能写出时间时间复杂度为 O(n) 和额外空间复杂度为 O(1) 的算法吗？
思路：双指针
代码来自讨论区jiafeilee的代码
class Solution {//执行用时 :25 ms, 在所有 Java 提交中击败了31.62%的用户
public boolean circularArrayLoop(int[] nums) {
int len = nums.length;
if(nums == null || len < 1)
return false;
for(int i=0;i<len;i++){
boolean[] visited = new boolean[len];//访问数组，用来记录数组中元素是否被访问
int j = i;
int count = 0;//判断循环元素长度
while(!visited[j]){
visited[j] = true;
if(nums[j] > 0){//向前移动
j = (j + nums[j]) % len;//新索引
if(nums[j] < 0)//相反方向
break;
count++;
}else{//向后移动
j = (j + nums[j]) % len >= 0 ? (j + nums[j]) % len : len + (j + nums[j]) %len;//新索引
if(nums[j] > 0)//相反方向
break;
count++;
}
if(j == i && count > 1)//循环完判断是否回到原点且长度大于1
return true;
}
}
return false;
}
}
524. 通过删除字母匹配到字典里最长单词中等
给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。
示例 1:
输入:s = "abpcplea", d = ["ale","apple","monkey","plea"]，输出: "apple"
示例 2:
输入:s = "abpcplea", d = ["a","b","c"]，输出: "a"
说明:
- 所有输入的字符串只包含小写字母。
- 字典的大小不会超过 1000。
- 所有输入的字符串长度不会超过 1000。
思路：
代码来自评论区Mr.Q的回答
class Solution {//执行用时 :30 ms, 在所有 Java 提交中击败了44.72%的用户
public String findLongestWord(String s, List<String> d) {
String longest = "";//在符合条件的target中，选出最长的下标标最小的
for (String target: d) {
int l1 = longest.length();
int l2 = target.length();
if (l1 > l2 || (l1 == l2 && longest.compareTo(target) < 0))
continue;
if(isSubstring(s,target)) {
longest = target;
}
}
return longest;
}
//筛选s中是否包含字典中的元素target
public boolean isSubstring(String s, String target){
int i = 0 ,j = 0;;
while(i < s.length() && j < target.length()){
if(s.charAt(i) == target.charAt(j)){
j++;
}
i++;
}
return j == target.length();
}
}
532. 数组中的K-diff数对简单
给定一个整数数组和一个整数 k, 你需要在数组里找到**不同的 **k-diff 数对。这里将 k-diff 数对定义为一个整数对 (i, j), 其中 i 和 j 都是数组中的数字，且两数之差的绝对值是 k.
示例 1:
输入: [3, 1, 4, 1, 5], k = 2
输出: 2
解释: 数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。
尽管数组中有两个1，但我们只应返回不同的数对的数量。
示例 2:
输入:[1, 2, 3, 4, 5], k = 1
输出: 4
解释: 数组中有四个 1-diff 数对, (1, 2), (2, 3), (3, 4) 和 (4, 5)。
示例 3:
输入: [1, 3, 1, 5, 4], k = 0
输出: 1
解释: 数组中只有一个 0-diff 数对，(1, 1)。
注意:
- 数对 (i, j) 和数对 (j, i) 被算作同一数对。
- 数组的长度不超过10,000。
- 所有输入的整数的范围在 [-1e7, 1e7]。
思路：双指针
class Solution {//执行用时 :5 ms, 在所有 Java 提交中击败了94.47%的用户
public int findPairs(int[] nums, int k) {
int len = nums.length;
if(nums == null || len < 1 || k < 0)
return 0;
Arrays.sort(nums);
int left = 0;
int right = 1;
int count = 0;
while(right < len){
int diff = nums[right] - nums[left];
if(diff < k){
right++;
}else if(diff > k){
left++;
}else{
count++;
right++;
left++;
}
while(left > 0 &&left < len && nums[left] == nums[left - 1]){
left++;
}
while(right < len && nums[right] == nums[right - 1]){
right++;
}
while(right <= left){
right = left + 1;
}
}
return count;
}
}
567. 字符串的排列中等
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1:
输入: s1 = "ab" s2 = "eidbaooo"，输出: True
解释: s2 包含 s1 的排列之一 ("ba").
示例2:
输入: s1= "ab" s2 = "eidboaoo"，输出: False
注意：
- 输入的字符串只包含小写字母
- 两个字符串的长度都在 [1, 10,000] 之间
思路：滑动窗口
class Solution {//执行用时 :8 ms, 在所有 Java 提交中击败了69.15%的用户
public boolean checkInclusion(String s1, String s2) {
int len1 = s1.length();// 匹配采用的窗口大小为s1串的大小
int len2 = s2.length();
if(len1 > len2)
return false;
int[] s1map = new int[26];
int[] s2map = new int[26];
//此循环计算每个字母的出现次数
for(int i=0;i<len1;i++){
//s1.charAt(i)-'a'将字符'a'映射到索引0,将'b'映射到索引1,依此类推('z'映射到索引25)
s1map[s1.charAt(i) - 'a']++;
s2map[s2.charAt(i) - 'a']++;
}
for(int i=len1;i<len2;i++){
if (matches(s1map, s2map))
return true;
//滑动窗口
s2map[s2.charAt(i-len1) - 'a']--;
s2map[s2.charAt(i) - 'a']++;
}
return matches(s1map, s2map);
}
public boolean matches(int[] s1map, int[] s2map) {
for (int i = 0; i < 26; i++) {
if (s1map[i] != s2map[i])
return false;
}
return true;
}
}
632. 最小区间困难
你有
k个升序排列的整数数组。找到一个最小区间，使得k个列表中的每个列表至少有一个数包含在其中。
我们定义如果b-a < d-c或者在b-a == d-c时a < c，则区间 [a,b] 比 [c,d] 小。
示例 1:
输入:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
输出: [20,24]
解释:
列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。
注意:
- 给定的列表可能包含重复元素，所以在这里升序表示 >= 。
- 1 <=
k<= 3500- -105 <=
元素的值<= 105- 对于使用Java的用户，请注意传入类型已修改为List<List<Integer>>。重置代码模板后可以看到这项改动。
思路：
713. 乘积小于K的子数组中等
给定一个正整数数组
nums。找出该数组内乘积小于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的子数组。
说明:
0 < nums.length <= 500000 < nums[i] < 10000 <= k < 10^6
思路：双指针
关键是知道这个等式怎么来的 res += right - left + 1，来自评论区的解释：
以[10,5,2,6] k=101 为例，注意是101！！！不是官方的100
第一次 L=0 ,R =0 , res = 0 + 0 - 0 + 1 =1 [10]的数量为1
第二次 L=0 R =1 , res = 1 + 1 - 0 + 1 =3 [10]的数量为1，[10,5]的数量为2+1
第三次 L=0 R =2, res = 3 + 2 - 0 + 1 =6 [10,5]的数量为2+1, [10,5,2]的数量为3+2+1
第四次 L=1 R= 3, res = 6 + 3 - 1 + 1 =9 [10,5,2]的数量为3+2+1，[10,5,2,6]的数量为3+3+2+1=9
可以看出，如果符合要求L,R,每一次的增量是在上一个的数量上增加了 L-R+1
class Solution {//执行用时 :9 ms, 在所有 Java 提交中击败了98.63%的用户
public int numSubarrayProductLessThanK(int[] nums, int k) {
if(nums == null || nums.length < 1)
return 0;
if(k == 0 || k == 1)
return 0;
int left = 0;
int prod = 1;//存储nums[left]~nums[right]的累积
int res = 0;
for(int right = 0; right < nums.length; right++){
prod *= nums[right];
while(prod >= k){
prod /= nums[left];
left++;
}
res += right - left + 1;
}
return res;
}
}
