双指针

算法中的双指针使用

双指针主要用来遍历数组，两个指针指向不同的元素，从而协同完成任务。

1、有序数组的Tow Sum

LeetCode的TowSum

题目描述：有序数组，找出两个数组，让和为target

算法思想：使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素，指向值较小元素的指针从头向后开始遍历，指向较大的指针从后向前开始遍历。

• 如果两个指针指向元素的和sum==target，返回结果位置
• 如果sum>target，则移动较大的指针
• 如果sum<target，则移动较小的指针

public int[] twoSum(int[] numbers,int target){
    int i=0,j=numbers.length-1;
    while(i<j){
        int sum=numbers[i]+numbers[j];
        if(sum==target){
            return new int[]{i+1,j+1};
        }else if(sum<target){
            i++;
        }else{
            j--;
        }
    }
    return null;
}

2、两数的平方和

LeetCode

题目描述：判断一个数是否为两个数的平方和

算法思想：还是使用两个指针，一个指针为0，一个指针为和的sqrt

• 如果两个指针指向元素的和powSum==target，返回结果位置
• 如果powSum>target，则移动较大的指针
• 如果powSum<target，则移动较小的指针

public boolean judgeSquerSum(int target){
    int i=0,j=(int)Math.sqrt(target);
    while(i<=j){//此处有等号，不然target=2的时候，没有等号就返回false
        int sum=i*i+j*j;
        if(sum==target){
            return true;
        }else if(sum<target){
            i++;
        }else{
            j--;
        }
    }
    return false;
}

判断链表是否有环

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null){
            return false;
        }
        ListNode slow=head,fast=head;//声明两个临时指针，都指向head
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
                return true;
            }
        }
        return false;
    }
}

赏

谢谢你请我吃糖果

支付宝

微信

• 本文作者： Victor Dan
• 本文链接： https://anonymousdq.github.io/victor.github.io/2019/09/01/双指针/
• 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！