先从已一道算法题目说起，题目如下
在一个数组中找到两个数、使得这两个数之差等于给定的 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;}
复制代码
评论