算法精选题总结之双指针法
1.有序数组中平方取值的种类
2.无重复字符的最长子串
3.删除链表的倒数第N个节点
4.数组中移除特定的元素
5.长度最小的子数组
6.数组中的最长山脉
1.有序数组中平方取值的种类
给你一个有序整数数组，数组中的数可以是正数、负数、零，请实现一个函数，这个函数返回一个整数：返回这个数组所有数的平方值中有多少种不同的取值。举例：
（1）nums = {-1,1,1,1},
那么你应该返回的是：1。因为这个数组所有数的平方取值都是1，只有一种取值
（2）nums = {-1,0,1,2,3}
你应该返回4，因为nums数组所有元素的平方值一共4种取值：1,0,4,9
核心思想：题目已经告诉当前数组有序，但是序列中会有负数，一说到有序数组我们就想到了双指针，可以一前一后两个指针分别控制来实现判断。核心的代码如下。
// Author:jefflee1314
public class Main {
public static void main(String[] args) {
Solution instance = new Solution();
int[] array = new int[]{-1,0,1,2,3};
int result = instance.solution(array);
System.out.println("result = " + result);
}
}
class Solution {
public int solution(int[] arr) {
int i=0;
int j=arr.length-1;
int count=0;
while(i<=j){
int tempI = Math.abs(arr[i]);
int tempJ = Math.abs(arr[j]);
if(tempI > tempJ) {
count++;
while(i<=j && Math.abs(arr[i])==tempI) {
i++;
}
}else if(tempI < tempJ) {
count++;
while(i<=j && Math.abs(arr[j])== tempJ) {
j--;
}
}else{
count++;
while(i<=j && Math.abs(arr[i])==tempI) {
i++;
}
while(i<=j && Math.abs(arr[j])== tempJ) {
j--;
}
}
}
return count;
}
}
2.无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
在暴力法中，我们会反复检查一个子字符串是否含有有重复的字符，但这是没有必要的。如果从索引 i 到 j - 1之间的子字符串 s_{ij}
已经被检查为没有重复字符。我们只需要检查 s[j]对应的字符是否已经存在于子字符串 s_{ij}中。
要检查一个字符是否已经在子字符串中，我们可以检查整个子字符串，这将产生一个复杂度为 O(n^2)的算法，但我们可以做得更好。
通过使用 HashSet 作为滑动窗口，我们可以用 O(1)的时间来完成对字符是否在当前的子字符串中的检查。
滑动窗口是数组/字符串问题中常用的抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 [i, j)（左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如，我们将 [i, j)向右滑动 1 个元素，则它将变为 [i+1, j+1)（左闭，右开）。
回到我们的问题，我们使用 HashSet 将字符存储在当前窗口 [i, j)（最初 j = i）中。 然后我们向右侧滑动索引 j，如果它不在 HashSet 中，我们会继续滑动 jj。直到 s[j] 已经存在于 HashSet 中。此时，我们找到的没有重复字符的最长子字符串将会以索引 i 开头。如果我们对所有的 ii 这样做，就可以得到答案。
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
// try to extend the range [i, j]
if (!set.contains(s.charAt(j))){
set.add(s.charAt(j++));
ans = Math.max(ans, j - i);
}
else {
set.remove(s.charAt(i++));
}
}
return ans;
}
}
3.删除链表的倒数第N个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
当前给定的n肯定是有效的。
核心思想：可以考虑另外使用两个指针，一个指针从head开始往后遍历，走n+1，另外一个节点开始遍历，然后两个节点开始相继往后，第一个指针到最后，第二个节点就到了前n+1的节点，那么可以开始删掉这个节点了。
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy;
ListNode second = dummy;
// Advances first pointer so that the gap between first and second is n nodes apart
for (int i = 1; i <= n + 1; i++) {
first = first.next;
}
// Move first to the end, maintaining the gap
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}
4.数组中移除特定的元素
给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 **val **的元素，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
核心思想：可以使用两个指针，一个遍历原数组，一个标记新数组，判断的条件就是元素时候和给定的val相等。
class Solution {
public int removeElement(int[] nums, int val) {
int i=0;
int j=0;
for(;i<nums.length && j<nums.length;) {
if(nums[i]!=val){
nums[j++]=nums[i];
}
i++;
return j;
}
public void printArray(int[] nums) {
for(int i=0;i<nums.length;i++) {
System.out.print(nums[i]);
System.out.print(" ");
}
System.out.println();
}
}
5.长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
核心思想：遇到这种题目，一定要想到两个指针的算法，用法比较巧妙，两个指针，同时出发，但是运动的过程中注意变换，right先走，left后走。
// Author:jefflee1314
public class Main {
public static void main(String[] args) {
Solution instance = new Solution();
int[] array = new int[]{1,2,3,4,5};
int result = instance.minSubArrayLen(15,array);
System.out.println("result = " + result);
}
}
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int left = 0;
int right = -1;
int length = nums.length + 1;
int sum = 0;
while(left < nums.length) {
if(sum < s && right < nums.length-1) {
right++;
sum += nums[right];
}else {
sum -= nums[left];
left++;
}
if(sum >= s) {
length = min(length, right-left+1);
}
}
if (length == nums.length + 1) return 0;
return length;
}
public int min(int a, int b) {
return a > b ? b : a;
}
}
6.数组中的最长山脉
我们把数组 A 中符合下列属性的任意连续子数组 B 称为 “山脉”：
B.length >= 3
存在 0 < i < B.length - 1 使得 B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]
给出一个整数数组 A，返回最长 “山脉” 的长度。
如果不含有 “山脉” 则返回 0。
输入：[2,1,4,7,3,2,5]
输出：5
解释：最长的 “山脉” 是 [1,4,7,3,2]，长度为 5。
class Solution
{
public int longestMountain(int[] A)
{
if (A.length < 3)
return 0;
int max = 0, count = 0;
boolean decrease = false;
for (int i = 0; i < A.length - 1; i++)
{
//count !=0,说明此前已经递增过了，现在开始计算递减。
if (count != 0 && A[i] > A[i + 1])
{
decrease = true;
count++;
}
//首先计算一下上坡长度。
if (!decrease)
count = A[i] < A[i + 1] ? count + 1 : 0;
else if(A[i] <= A[i + 1])
{
decrease = false;
max = max > count + 1 ? max : count + 1;
count = A[i] == A[i + 1] ? 0 : 1;
}
if (i == A.length - 2 && decrease && A[i] > A[i + 1])
max = max > count + 1 ? max : count + 1;
}
return max;
}
}
