双指针法

所谓双指针，指的是在遍历对象的过程中，使用两个相同方向或者相反方向的指针进行扫描，从而达到相应的目的。

例题一：盛最多水的容器「左右指针」

给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水的最大值为 49。
解法：这种方法背后的思路在于，两线段之间形成的区域总是会受到其中较短那条长度的限制。此外，两线段距离越远，得到的面积就越大。

我们在由线段长度构成的数组中使用两个指针，一个放在开始，一个置于末尾。 此外，我们会使用变量 max 来持续存储到目前为止所获得的最大面积。 在每一步中，我们会找出指针所指向的两条线段形成的区域，更新 max，并将指向较短线段的指针向较长线段那端移动一步。

	public int maxArea(int[] height) {
        if(height.length==0) return 0;
		int max=(height.length-1)*Math.min(height[0],height[height.length-1]);	//最大面积初始化
		for(int l=0,r=height.length-1;l<r;) {
			if (height[l]<height[r]) {	// 左高度  < 右高度
				int temp=height[l];
				while(height[l]<=temp&&r>l) l++;//左指针右移（如果下个左指针<=当前指针，一直向下走）
			} else {					// 左高度 >= 右高度
				int temp=height[r];
				while(height[r]<=temp&&r>l) r--;//右指针左移（如果下个右指针<=当前指针，一直向下走）
			}
			max=Math.max(max,(r-l)*Math.min(height[l],height[r]));	//取得最大面积
		}
		return max;
	}

例题二：三数之和「左右指针」

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，

	满足要求的三元组集合为：
	[
		 [-1, 0, 1],
		 [-1, -1, 2]
	]

固定三个指针中最左（最小）数字的指针 i，双指针 j，k 分设在数组索引 (i+1, nums.length-1) 两端，通过双指针交替向中间移动，记录 nums[i] + nums[j] + nums[k] == 0 时的nums组合：

	public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> List = new ArrayList<List<Integer>>();
        if(nums.length < 3) return List;
        Arrays.sort(nums); // 进行排序
        for (int i = 0; i < nums.length ; i++) {
            if(nums[i] > 0) break; // nums[i]大于0，则三数之和大于0，所以结束跳出
            if(i > 0 && nums[i] == nums[i-1]) continue; // 去掉重复
            for(int j=i+1,k=nums.length-1;j < k;){
                int He = nums[i] + nums[j] + nums[k];
                if(He == 0){
                	List.add(Arrays.asList(nums[i],nums[j],nums[k]));
                    while (j<k && nums[j] == nums[j+1]) j++; // 去掉左重复
                    while (j<k && nums[k] == nums[k-1]) k--; // 去掉右重复
                    j++; k--;
                }
                else if (He < 0) j++;
                else if (He > 0) k--;
            }
        }
        return List;
    }

例题三：最接近的三数之和「左右指针」

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：
给定数组 nums = [-1，2，1，-4], 和 target = 1.

	满足要求的三元组集合为：
	与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2)

与三数之和类似。三数之和要求找到三个元素之和为0的所有不重复情况，这里找到三个元素之和最接近目标值的情况（唯一）。首先对原数组排序，然后维护一个绝对差值变量和对应的结果变量。遍历数组，使用双指针j和k，根据三数之和与目标值的大小关系来移动指针，注意跳过重复情况，并记录与目标值的最小绝对差和对应的三数之和。

	public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
     	int He,min;
     	if(nums.length<3)return target;
     	min=nums[0]+nums[1]+nums[2];
     	for(int i=0;i<nums.length-2;i++) {
     		if(i!=0) while (nums[i]==nums[i-1]&&i<nums.length-2) i++;
     		for(int j=i+1,k=nums.length-1;j<k;) {
     			He=nums[i]+nums[j]+nums[k];
     			if(He<target) {
     				if(target-He<Math.abs(min-target))min=He;
     				j++;
     			}
     			else if(He>target) {
     				if(He-target<Math.abs(min-target))min=He;
     				k--;
     			}
     			else return target;
     		}
     	}
     	return min;
    }

例题四：四数之和「左右指针」

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
	[
		 [-1,  0, 0, 1],
		 [-2, -1, 1, 2],
		 [-2,  0, 0, 2]
  	]

和3数之和类似，先将数组排序固定两个元素在用两个指针，一个指向头，一个指向尾，看四数之和为多少，太大了右指针左移，太小了左指针右移。

	public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> List = new ArrayList<List<Integer>>();
     	Arrays.sort(nums);
     	int He;
     	for(int i=0;i<nums.length-3;i++) {
     		if(i!=0&&nums[i-1]==nums[i]) continue;//防止重复
	     	for(int j=i+1;i<j&&j<nums.length-2;j++) {
	     		if(j!=i+1&&nums[j-1]==nums[j]) continue;//防止重复
	     		if(nums[j]>0&&nums[i]+nums[j]>target) break;
	     		for(int k=j+1,l=nums.length-1;k<l;) {
	     			He=nums[i]+nums[j]+nums[k]+nums[l];
	     			if(He<target)k++;
	     			else if(He>target)l--;
	     			else {
	     				List.add(Arrays.asList(nums[i],nums[j],nums[k],nums[l]));
	             		while(nums[k]==nums[k+1]) {
	             			k++;
	             			if(k>=l)break;
	             		}
	              		while(nums[l]==nums[l-1]) {
	               			l--;
	               			if(k>=l)break;
	               		}
	               		k++;
	               		l--;
	     			}
	     		}
	     	}
     	}
     	return List;
    }

例题五：删除链表的倒数第N个节点「快慢指针」

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

  	给定一个链表: 1->2->3->4->5, 和 n = 2.
  	
当删除了倒数第二个节点后，链表变为 1->2->3->5.

我们可以使用两个指针而不是一个指针。第一个指针从列表的开头向前移动 n+1 步，而第二个指针将从列表的开头出发。现在，这两个指针被 n 个结点分开。我们通过同时移动两个指针向前来保持这个恒定的间隔，直到第一个指针到达最后一个结点。此时第二个指针将指向从最后一个结点数起的第 n 个结点。我们重新链接第二个指针所引用的结点的 next 指针指向该结点的下下个结点。

	/**
 	* 链表数据结构
 	* class ListNode {
 	*     int val;
 	*     ListNode next;
	*     ListNode(int x) { val = x; }
 	* }
	*/
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode i=head,j=head;
    	for(;n>0;n--,j=j.next);	//后指针向后转移n次
    	if(j==null)return head.next;
    	for(;j.next!=null;) {	//前指针，后指针同时后指，直到后指针为null
    		i=i.next;
    		j=j.next;
    	}
    	i.next=i.next.next;//删除第n个结点
    	return head;
    }

例题六：环形链表「快慢指针」

给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

示例：

  	输入：head = [3,2,0,-4], pos = 1
	输出：true
	解释：链表中有一个环，其尾部连接到第二个节点。

通过使用具有 不同速度 的快、慢两个指针遍历链表，空间复杂度可以被降低至 O(1)。慢指针每次移动一步，而快指针每次移动两步。

如果列表中不存在环，最终快指针将会最先到达尾部，此时我们可以返回 false。

现在考虑一个环形链表，把慢指针和快指针想象成两个在环形赛道上跑步的运动员（分别称之为慢跑者与快跑者）。而快跑者最终一定会追上慢跑者。这是为什么呢？考虑下面这种情况（记作情况 A）- 假如快跑者只落后慢跑者一步，在下一次迭代中，它们就会分别跑了一步或两步并相遇。

	/**
 	* 链表数据结构
 	* class ListNode {
 	*     int val;
 	*     ListNode next;
	*     ListNode(int x) { val = x; }
 	* }
	*/
    public boolean hasCycle(ListNode head) {
        if(head!=null&&head.next!=null) {
    		ListNode  m=head,k=head.next.next;
    		while(m!=null&&k!=null) {
    			if(m==k)return true;
    			m=m.next;
    			if(k.next!=null)k=k.next.next;
    			else return false;
    		}
    	}
    	return false;
    }

例题七：环形链表II「快慢指针」

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

示例：

  	输入：head = [3,2,0,-4], pos = 1
	输出：链表中有一个环，其尾部连接到第二个节点。

通过使用具有 不同速度 的快、慢两个指针遍历链表，空间复杂度可以被降低至 O(1)。慢指针每次移动一步，而快指针每次移动两步。

第一次相遇时，假设慢指针 m 走了 t 步，那么快指针 k一定走了 2t 步，也就是说比 m 多走了 t 步（也就是环的长度）。
设相遇点距环的起点的距离为 l，那么环的起点距头结点 head 的距离为 t - l，也就是说如果从 head 前进 t - l 步就能到达环起点。
巧的是，如果从相遇点继续前进 t - l 步，也恰好到达环起点。

	/**
 	* 链表数据结构
 	* class ListNode {
 	*     int val;
 	*     ListNode next;
	*     ListNode(int x) { val = x; }
 	* }
	*/
    public ListNode detectCycle(ListNode head) {
        if (head == null) return null;
        ListNode m = head,k = head;
        while (k!=null&&k.next!=null) {
            m=m.next;
            k=k.next.next;
            if (m==k) break;
        }
        if(k==null) return null;
        else if(k.next==null) return null;
        while (head!=k) {
            head=head.next;
            k=k.next;
        }
        return head;
    }

例题八：快乐数「快慢指针」

编写一个算法来判断一个数是不是“快乐数”。
一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。

示例：

			输入: 19
			输出: true
			解释: 
			12 + 92 = 82
			82 + 22 = 68
			62 + 82 = 100
			12 + 02 + 02 = 1

使用“快慢指针”思想找出循环：“快指针”每次走两步，“慢指针”每次走一步，当二者相等时，即为一个循环周期。此时，判断是不是因为1引起的循环，是的话就是快乐数，否则不是快乐数。

	public boolean isHappy(int n) {
        int m=n,k=bitSquareSum(n);
        while(m!=k){
            m=bitSquareSum(m);
            k=bitSquareSum(bitSquareSum(k));
        }
        return m==1;
    }
    public int bitSquareSum(int n) {
        int sum = 0;
        for(;n>0;n=n/10){
            int t=n%10;
            sum+=t*t;
        }
        return sum;
    }

最后

以上就是温暖板凳为你收集整理的双指针法双指针法的全部内容，希望文章能够帮你解决双指针法双指针法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。