双指针

  • 双指针的核心思想是优化时间,将朴素的两重循环O(n ^ 2)算法优化成O(n)
O(n ^ 2)
for(int i - 0; i < n; i ++ )
	for(int j = 0; j < n; j ++ )
		exec()
将上面的朴素算法优化成O(n)
  • 双指针的通用框架
for(int i = 0, j = 0; i < n; i ++ ) {
	while(j < i && check(i, j)) j ++;
	//每道题目的具体逻辑
}
  • 一个简单的例子：输入一个字符串，将其中的每个单词单独输出
int main() {
	char str[1000];
	gets(str);
	int n = strlen(n);
	for(int i = 0; i < n; i ++ ) {
	    int j = i;
	    while(j < n && str[i] != ' ') j ++ ;
	
	    for(int k = i; k < j; k ++ ) cout << str[k];
	    cout << endl;
	    i = j;
	}
	
	return 0;
}
  • 单调性

最长连续不重复子序列

双指针

目录

1.快慢指针

快慢指针一般都初始化指向链表的头节点head,前进时快指针fast在前，慢指针slow在后

1.1 判断链表中是否含有环

解法思路：两个指针，一个每次前进两步，一个每次前进一步。如果不含有环，跑得快的那个指针最终会遇到Null；如果含有环，快指针最终会超慢指针一圈，和慢指针相遇，说明链表含有环。

boolean hasCycle(ListNode head){
	ListNode fast,slow;
	fast = slow = head;
	while (fast != null && fast.next != null){
		fast = fats.next.next;
		slow = slow.next;
	
		if (fast == slow) return true;
	}
	return false;
}

1.2 已经知道链表中含有环，返回环的位置

ListNode detectCycle(ListNode,head){
	ListNode fast,slow;
	fast = slow = head;
	while (fast != null && fast.next != null){
		fast = fast.next.next;
		slow = slow.next;
		if(fast == slow)break;
	}
	slow = head;
	while(slow != fast){
		fast = fast.next;
		slow = slow.next;
	}
	return slow;
}

1.3 寻找链表的中点

ListNode slow,fast;
slow = fast = head;
while(fast != null && fast.next != null){
	fast = fast.next.next;
	slow = slow.next;
}
return slow;

如果链表的长度时奇数，slow恰好停留在中点位置，如果为偶数，slow最终的位置是中点偏右

1.4 寻找链表中倒数第k个元素

ListNode slow,fast;
slow = fast = head;
while( k-- > 0) fast = fast.next;//让快指针先走k步，之后快慢指针同步推进
while(fast != null){
	slow = slow.next;
	fast = fast.next;
}
return slow;

1.5 第26题：删除排序数组中的重复项

class Solution{
public:
    int removeDuplicates(vector<int>& nums){
        if(nums.size() == 0){
            return 0;
        }
        int slow = 0, fast = 0;
        while(fast < nums.size()){
            if(nums[fast] != nums[slow]){
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }
        return slow+1;
    }
};

2.左右指针

左右指针在数组中实际是指两个索引值，一般初始化为left = 0, right = length -1

2.1 二分查找

int binarySearch(int[] nums, int target){
	int left = 0;
	int right = nums.length - 1;
	while(left < right){
		int mid = (right + left)/2;
		if (nums[mid] == target)
			return mid;
		else if (nums[mid] < target)
			left = mid + 1;
		else if (nums[mid] > target)
			right = mid - 1;
	}
	return -1;
}

2.2 两数之和

int [] twoSum(int[] nums, int target){
	int left = 0, right = nums.length -1;
	while(left < right){
	int sum = nums[left] + nums[right];
	if(sum == target)
		return new int[]{left+1,right+1};
	else if(sum < target)left++;
	else if(sum > target)right--;
	}
	return new int[]{-1,-1};
}

2.3 反转数组

void reverse(int[] nums){
	int left = 0;
	int right = nums.length -1;
	while (left < right){
		int temp = nums[left];
		nums[left] = nums[right];
		nums[right] = temp;
		left++;right--;
	}
}

3.二分查找

参考文章

  • 二分查找的思路很明确，难点在于处理边界条件，在处理时要关注“循环不变量”，并在整个程序过程中一以贯之，具体来讲：

  • 1）采用“左闭右闭”：

    int left = 0,right = length - 1;
while(left <= right){
    mid = left + (right - left)/2;
    ...
    left = mid + 1;
    ...
    right = mid - 1;
}

  • 2）采用“左闭右开”：

    int left = 0, right = length;
while(left < right){
    mid = left + (right - left)/2;
    ....
    left = mid + 1;
    ....
    right = mid;
}

3.1 二分查找框架

int binarySearch(int[] nums,int target){
	int left = 0,	right = ...;

	while(...){
		int mid = left + (right-left)/2;
		if(nums[mid] == target){
			...
		} else if(nums[mid] < target){
			left = ...
		} else if(nums[mid] > target){
			right = ...
		}
	}
	return ...;
}

3.2 寻找一个数

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 注意

    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
    }
    return -1;
}

思考：

1、为什么 while 循环的条件中是 <=，而不是 <？

2、为什么left = mid + 1，right = mid - 1？我看有的代码是right = mid或者left = mid，没有这些加加减减，到底怎么回事，怎么判断？

3.3 寻找左侧边界的二分查找

int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意

    while (left < right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}
为什么该算法能够搜索左侧边界**？

答：关键在于对于nums[mid] == target这种情况的处理：

    if (nums[mid] == target)
        right = mid;

可见，找到 target 时不要立即返回，而是缩小「搜索区间」的上界right，在区间[left, mid)中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。

3.4 寻找右侧边界的二分查找

int right_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;

    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left - 1; // 注意
}

3.5 逻辑统一

对于寻找左右边界的二分搜索，常见的手法是使用左闭右开的「搜索区间」，根据逻辑将「搜索区间」全都统一成了两端都闭，便于记忆，只要修改两处即可变化出三种写法：

int binary_search(int[] nums, int target) {
    int left = 0, right = nums.length - 1; 
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            // 直接返回
            return mid;
        }
    }
    // 直接返回
    return -1;
}

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定左侧边界
            right = mid - 1;
        }
    }
    // 最后要检查 left 越界的情况
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}


int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定右侧边界
            left = mid + 1;
        }
    }
    // 最后要检查 right 越界的情况
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/huhu555/p/14650892.html