写点什么

双指针算法之同向双指针

用户头像
泽睿
关注
发布于: 2 小时前

先从已一道算法题目说起,题目如下


在一个数组中找到两个数、使得这两个数之差等于给定的 target,不使用额外的空间。


拿到这道题目、可以分析一下 ,我们知道要查找一个数是否在数组中是否存在,我们可以使用 hash 表来判断,但是此道题目不能使用额外空间。那么我么就要舍弃 hash 表,那么有么有一种方式来判断一个数在不在一个数组中出现,其实是有的。


我们知道可以使用二分法,也就是说可以用二分法来代替 hash 表。 数组外加二分可以起到 hash 表的作用的。


我们可以看看二分法是如何实现的。


public int[] twoDiff(int[] nums, int target) {    if (nums == null || nums.length < 2) {        return new int[]{-1, -1};    }    target = Math.abs(target);//这里主要是考虑target有可能为负数,    for (int i = 0; i < nums.length; i++) {        int j = binarySearch(nums, i + 1, nums.length - 1, target + nums[i]);        if (j != -1) {            return new int[]{nums[i], nums[j]};        }    }    return new int[]{-1, -1};}
private int binarySearch(int[] nums, int left, int right, int target) { while (left + 1 < right) {//left,right 相邻的时候结束循环 int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } if (nums[mid] < target) { left = mid; } else { right = mid; } } if (nums[left] == target){ return left; } if (nums[right] == target){ return right; } return -1;}
复制代码


上面的时间复杂度的是 nlogn(二分查找的过程是 logn),那么有没有其他更优的方式,使得时间复杂度更低呢 O(n)的时间复杂度呢?


O(n)的算法我们可能会想到用双指针,双指针有同向双指针,相向双指针,那么这种属于是那种情况呢? 其实这个题目就是同向双指针的典型用法。为什么这么说呢,我们来分析一下,当 i 指针向右边移动的时候,满足 nums[j] - nums[i] = target 的 j 也会向右移动,没有必要去在 i+1 ~ j-1 之间寻找。我们来看看这道题目的的双指针写法。


//最差的情况下 i和j各自都走了n次、因为j指针永远不会回退、所以j最差情况走了n此//i指针最差情况下也走了n次、所以综合来说时间复杂度是O(2n)//同向双指针、时间复杂度是N、因为j指针永远不会回头。跟传统的两个for循环、j每次都从0开始回头不一样、注意区别。//这里i、j指针都是一直往下走的。//还有一种理解就是 两个指针分别访问数组中的元素一次、所以时间复杂度是O(n)public static int[] twoDiff(int[] nums, int target) {    if (nums == null || nums.length < 2) {        return new int[]{-1, -1};    }    int j = 1;    for (int i = 0; i < nums.length; i++) {        j = Math.max(j, i + 1);////这里主要是考虑、有可能j是落后于i的。所以需要保证j永远你在i的右边, 为了处理此种异常 [0,1,2,2] 0        while (j < nums.length && nums[j] - nums[i] < target) {            j++;        }        if (j >= nums.length) {            break;        }        if (nums[j] - nums[i] == target) {            return new int[]{nums[i], nums[j]};        }    }    return new int[]{-1, -1};}
复制代码


上面注释中也解释了双指针算法中的时间复杂度是 O(n),注意和传统的两个 for 循环的区别。


根据上面的题目我们可以总结出同向双指针的模板代码:


j = 0 or j= 1for i from 0 to (m-1)  while j < n and (i,j 的搭配不满足条件)    j += 1  if (i,j 的搭配满足条件)    处理i,j的这次搭配
复制代码


讲解了同向双指针算法、我们来看几道类似的模板题目。


全零子串问题: 求出字符串中全 0 子串的个数, 001000 有 5 个 0,3 个 00,共 9 个子串


public static int stringCount(String str) {    if (str == null) {        return 0;    }    int j      = 1;    int answer = 0;    for (int i = 0; i < str.length(); i++) {        if (str.charAt(i) != '0') {            continue;        }        j = Math.max(j, i + 1);//这里主要是考虑、有可能j是落后于i的。所以需要保证j永远你在i的右边        while (j < str.length() && str.charAt(j) == str.charAt(i)) {            j++;        }      //实际上就是从当前i开始统计i到最近一个不是0的个数,然后将所有的这些i相加在一起就是answer        answer += (j - i);    }    return answer;}
复制代码


数组去重,去掉未排序数组中的重复元素, [1,3,1,2,0,2] ==> [1,2,3,0,?,?] 要求在原数组上进行操作,也就是额外空间复杂度 O(1)


public int removeDuplicates(int[] nums) {    if (nums == nums) {        return 0;    }  	 //先排序    Arrays.sort(nums);    int j = 1;    int i;    for (i = 0; i < nums.length; i++) {        while (j < nums.length && nums[j] == nums[i]) {            j++;        }        if (j == nums.length){            break;        }        nums[i + 1] = nums[j];    }    return i + 1;}
复制代码


用户头像

泽睿

关注

还未添加个人签名 2017.12.22 加入

还未添加个人简介

评论

发布
暂无评论
双指针算法之同向双指针