双指针的题目中一般有明显的两个条件：最大最小、最左最右...
找到移动两个指针的条件：
例如算最大差值，则next > current，移动max指针并计算差值，next < current，移动min + max指针
例如算最大面积，先在左右端点，往中间移动，每次移动小边
【leetcode.121 买卖股票的最佳时机】
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。class Solution {
public int maxProfit(int[] prices) {
int min = 0;
int max = 0;
int result = 0;
for (int i = 0; i < prices.length; i ++) {
if (prices[i] > prices[min]) {
max = i;
int temp = prices[max] - prices[min];
result = Math.max(temp, result);
} else {
min = i;
max = min;
}
}
return result;
}
}典型的双指针，因为题目里找最大利润，即一个最大，一个最小
【leetcode11. 盛水最多的容器】
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
class Solution {
public int maxArea(int[] height) {
// 双指针：代表两个边界，每次移动小边
// 为什么是小边？因为假设t是宽，min(x,y)是高，如果min(x,y)结果是x，如果移动y，新的y比x大，那就是宽缩小了，高不变，如果新的y比x小，那就是宽缩小，高也缩小
int x = 0;
int y = height.length - 1;
int area = 0;
while (true) {
if (y <= x) {
break;
}
int temp = (y - x) * Math.min(height[x], height[y]);
area = Math.max(area, temp);
if (height[x] <= height[y]) {
x += 1;
} else {
y -= 1;
}
}
return area;
}
}【leetcode.202 快乐数 - 快慢指针】
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
此题中提到一个点：要么无限循环，要么到达终点——1。应对无限循环的问题，一定是双指针中的快慢指针，快慢指针有两个要点：
要动，一个动得快，一个动的慢，体现在java上就是一个getNext(n)，一个是getNext(getNext(n))
不动的很可能进入不了循环
如果会无限循环，最终只有一个结果：在某一个点上两个指针相遇，如果不能循环，则快指针一定会到达终点
class Solution {
public boolean isHappy(int n) {
if (n == 1) {
return true;
}
int slow = n;
int fast = getNext(n);
while (true) {
if (slow == fast) {
return false;
} else if (fast == 1) {
return true;
}
slow = getNext(slow);
fast = getNext(getNext(fast));
}
}
public int getNext(int n) {
char[] charArray = String.valueOf(n).toCharArray();
int sum = 0;
for (char c : charArray) {
sum += Integer.parseInt(String.valueOf(c)) * Integer.parseInt(String.valueOf(c));
}
return sum;
}
}【leetcode. 26、27 移除元素】
26题，移除重复元素，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。class Solution {
public int removeDuplicates(int[] nums) {
int index = 0;
for (int num : nums) {
if (index == 0) {
index += 1;
continue;
}
if (num != nums[index - 1]) {
nums[index] = num;
index += 1;
}
}
return index;
}
}27题，删除特定元素：
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。class Solution {
public int removeElement(int[] nums, int val) {
int index = 0;
for (int num : nums) {
if (num != val) {
nums[index] = num;
index += 1;
}
}
return index;
}
}这两个题使用双指针，因为有一个很明显的题意：移除并往前插
这就意味着有一个指针正常遍历，有一个指针落后，即双指针问题
如果想不到使用双指针，暴力破解也是可以的，只是会麻烦一点，效率也不高，因此它非常典型
【leetcode.76 最小覆盖字串 - 双边指针】
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。这道题的双指针解法就是：
如果覆盖，左边移动，如果不覆盖，右边移动
可以设置一个标志位，判定在while循环中是哪边进行移动
class Solution {
public String minWindow(String s, String t) {
if (t.length() > s.length()) {
return "";
}
int left = 0;
int right = 0;
Map<Character, Integer> tMap = buildDict(t);
Map<Character, Integer> sMap = new HashMap<>();
char[] sChar = s.toCharArray();
String result = "";
boolean contains = false;
while (true) {
if (right > s.length() - 1 || left > s.length() - 1) {
break;
}
if (!contains) {
if (sMap.containsKey(sChar[right])) {
Integer i = sMap.get(sChar[right]);
i += 1;
sMap.put(sChar[right], i);
} else {
sMap.put(sChar[right], 1);
}
}
if (checkContains(sMap, tMap)) {
if (result == "") {
result = s.substring(left , right+1);
} else {
result = result.length() < (right - left + 1) ? result : s.substring(left , right+1);
}
Integer i = sMap.get(sChar[left]);
i -= 1;
sMap.put(sChar[left], i);
left += 1;
contains = true;
} else {
right += 1;
contains = false;
}
}
return result;
}
public boolean checkContains(Map<Character, Integer> ori, Map<Character, Integer> tar) {
for (Map.Entry<Character, Integer> oneTar : tar.entrySet()) {
Character targetAlphabet = oneTar.getKey();
if (ori.get(targetAlphabet) == null || ori.get(targetAlphabet) < oneTar.getValue()) {
return false;
}
}
return true;
}
public Map<Character, Integer> buildDict(String t) {
char[] array = t.toCharArray();
Map<Character, Integer> result = new HashMap<>();
for (char a : array) {
if (result.containsKey(a)) {
Integer i = result.get(a);
i += 1;
result.put(a, i);
} else {
result.put(a, 1);
}
}
return result;
}
}【leetcode.15 三数之和】
给你一个整数数组 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] 。
注意，输出的顺序和三元组的顺序并不重要。这个题是三个数，确定一个数，另外两个就可以是一个双指针了
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Set<ThreeHolder> set = new HashSet<>();
Arrays.sort(nums);
int i = 0;
List<List<Integer>> result = new ArrayList<>();
while (i < nums.length && nums[i] <= 0) {
int j = i + 1, k = nums.length - 1;
while (j < k) {
if (nums[j] + nums[k] > -1 * nums[i]) {
k -= 1;
} else if (nums[j] + nums[k] < -1 * nums[i]) {
j += 1;
} else {
ThreeHolder th = new ThreeHolder(nums[i], nums[j], nums[k]);
if (set.add(th)) {
result.add(th.toList());
}
k -= 1;
j += 1;
}
}
i += 1;
}
return result;
}
public class ThreeHolder {
private int num1;
private int num2;
private int num3;
public ThreeHolder(int num1, int num2, int num3) {
this.num1 = num1;
this.num2 = num2;
this.num3 = num3;
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || o.getClass() != getClass()) {
return false;
}
ThreeHolder that = (ThreeHolder) o;
return num1 == that.num1 && num2 == that.num2 && num3 == that.num3;
}
@Override
public int hashCode() {
return Objects.hash(num1, num2, num3);
}
public List<Integer> toList() {
return new ArrayList<>() {{
add(num1);
add(num2);
add(num3);
}};
}
}
}【leetcode.209 长度最小的子数组】
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。此题是滑窗，本质其实还是双指针
有两个思路：
像11题容器一样，从头尾开始缩小，谁小缩谁，但是这么做发现要用递归，而且这个题是把端点值算进去的，因此当两边相等的时候，要双判，增加难度
思路2就是从小到大，如果大于等于target，移动end扩大窗口，否则移动start缩小窗口，这就是滑窗的思路
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int start = 0, end = 0;
int minSize = Integer.MAX_VALUE;
int current = nums[0];
while (start < nums.length && end < nums.length) {
if (current >= target) {
minSize = Math.min(minSize, end - start + 1);
if (start < end) {
current -= nums[start];
start += 1;
} else {
current -= nums[start];
start += 1;
end += 1;
if (end < nums.length) {
current += nums[end];
}
}
} else {
end += 1;
if (end < nums.length) {
current += nums[end];
}
}
}
if (minSize == Integer.MAX_VALUE) {
return 0;
}
return minSize;
}
}
评论区