有些情况，我们需要对数据根据ID值做出匹配。比如对于供应商来说，一堆货物需要发货，全部把订单号以及一些用户信息传给快递公司获取快递单号。
很可能得到类似这种形式的数据（注意，此处订单号和快递单号均为虚拟） ，因为疫情原因，或者超出快递公司配送区域，拿到的快递单号，会比实际需要的少。这种时候，双指针就可以大显身手了：
我们发现，这个过程，从头到尾扫描一遍即可完成，时间复杂度O(n)，这个过程，比不使用双指针要快的多，以下是上述过程是否使用双指针的代码对比。
使用双指针：
import java.util.*;
public class Main {
public static void main(String[] args){
List orders = Main.getInitOrders();
List responses = getExpressResponses();
int orderSize = orders.size();
int responseSize = responses.size();
int i = 0;
int j = 0;
while(i getExpressResponses(){
String[] rspIds = new String[]{"taobao1","taobao3"};
String[] rspExpresses = new String[]{"express1","express2"};
List responses = new ArrayList<>();
for(int i = 0; i < rspIds.length; i++){
responses.add(ExpressResponse.init(rspIds[i],rspExpresses[i]));
}
return responses;
}
private static List getInitOrders(){
String[] ids = new String[]{"taobao1","taobao2","taobao3"};
List orders = new ArrayList<>();
for (String id : ids) {
orders.add(MyOrder.init(id));
}
return orders;
}
static class MyOrder{
String orderId;//订单号
String expressCode;//快递单号
public static MyOrder init(String orderId){
MyOrder order = new MyOrder();
order.orderId = orderId;
return order;
}
@Override
public String toString() {
return "{orderId:"+orderId+",expressCode:"+expressCode+"}";
}
}
static class ExpressResponse{
String orderId;//订单号
String expressCode;//快递单号
public static ExpressResponse init(String orderId,String expressCode){
ExpressResponse response = new ExpressResponse();
response.orderId = orderId;
response.expressCode = expressCode;
return response;
}
}
}
不用双指针：
import java.util.*;
public class Main {
public static void main(String[] args){
List orders = Main.getInitOrders();
List responses = getExpressResponses();
for(MyOrder order:orders){
for(ExpressResponse response:responses){
if(order.orderId!=null && order.orderId.equals(response.orderId)){
order.expressCode = response.expressCode;
}
}
}
System.out.println(orders);
}
private static List getExpressResponses(){
String[] rspIds = new String[]{"taobao1","taobao3"};
String[] rspExpresses = new String[]{"express1","express2"};
List responses = new ArrayList<>();
for(int i = 0; i < rspIds.length; i++){
responses.add(ExpressResponse.init(rspIds[i],rspExpresses[i]));
}
return responses;
}
private static List getInitOrders(){
String[] ids = new String[]{"taobao1","taobao2","taobao3"};
List orders = new ArrayList<>();
for (String id : ids) {
orders.add(MyOrder.init(id));
}
return orders;
}
static class MyOrder{
String orderId;//订单号
String expressCode;//快递单号
public static MyOrder init(String orderId){
MyOrder order = new MyOrder();
order.orderId = orderId;
return order;
}
@Override
public String toString() {
return "{orderId:"+orderId+",expressCode:"+expressCode+"}";
}
}
static class ExpressResponse{
String orderId;//订单号
String expressCode;//快递单号
public static ExpressResponse init(String orderId,String expressCode){
ExpressResponse response = new ExpressResponse();
response.orderId = orderId;
response.expressCode = expressCode;
return response;
}
}
}
假设订单列表长度为n，则使用双指针效率为 ,不使用双指针效率为 。
这意味着，使用双指针之后，整个处理效率将大量提升，能有效增加运单号处理的效率。
4.1 经典双指针场景 4.1.1 碰撞指针已知一个有序数组 nums ，元素无重复,求有多少对数对满足 i < j 且 nums[i]+nums[j]==0
public class Main {
public static void main(String[] args){
Main solution = new Main();
System.out.println(solution.getPairCnt(new int[]{-7,-5,-2,0,0,1,2,3,5}));
}
private int getPairCnt(int[] nums){
if(nums == null || nums.length < 2)
return 0;
int j = nums.length-1;
int ans = 0;
for(int i = 0; i < j; i++){
while (i0){
--j;
}
if(i
使用指针碰撞来减少循环次数，可成功解出数对数目。当然，这题也可以用哈希表。
双指针和哈希表性能对比
双指针 哈希表 有序 时间复杂度O(n)，空间复杂度O(1) 时间复杂度O(n)，空间复杂度O(n) 无序 要排序，时间复杂度O(nlogn)，空间复杂度O(1) 时间复杂度O(n)，空间复杂度O(n)
有的时候，使用双指针不是为了减少时间复杂度，而是减少前期计算难度。例如判断一个字符串是不是回文数：
public class Main {
public static void main(String[] args){
Main solution = new Main();
System.out.println(solution.isPalinedromes("aaabbaaa"));
System.out.println(solution.isPalinedromes("aabbbaaa"));
System.out.println(solution.isPalinedromes2("aaabbaaa"));
System.out.println(solution.isPalinedromes2("aabbbaaa"));
}
//双指针遇见方式结束
private boolean isPalinedromes(String s){
if(s == null || s.length() == 0)
return true;
int i = 0;
int j = s.length()-1;
while(i=j;
}
//计算方式计算出对称点
private boolean isPalinedromes2(String s){
if(s == null || s.length() == 0)
return true;
int n = s.length();
for(int i = 0; i < n/2; i++){
if(s.charAt(i)!=s.charAt(n-i-1))
return false;
}
return true;
}
}
这里有两种方式，一种是通过找碰撞点确定不重复，一种通过计算分割点和对称点确定不重复，使用第一种方式，可减少计算对称点位置计算这部分操作，从而减少产生bug的可能。
4.1.2 快慢指针
给你一个有序列表，存在大量的重复。请你在当前数据列中原地进行去重操作，返回去重后的有效长度。
public class Main {
public static void main(String[] args){
Main solution = new Main();
int[] arr = new int[]{1,1,1,2,3,3,4,5,5,5,5,5};
System.out.println(solution.getList(arr));
System.out.println(Arrays.toString(arr));
}
private int getList(int[] arr){
if(arr==null||arr.length==0)
return 0;
int slow = 0;
int n = arr.length;
for(int fast = 1; fast < n; fast++){
if(arr[fast]!=arr[slow])
++slow;
arr[slow] = arr[fast];
}
return slow+1;
}
}
策略如下：
1. 假设fast和slow位置的值相同，则进行赋值（实际不会改变slow的值）
2. 假设fast和slow位置的值不相同，移动slow指针，再进行赋值
3. slow最终指向最后一个去重位置，那slow+1则代表了这一段数组的长度
喜欢的话，点个赞吧~！平时做题，以及笔记内容将更新到公众号。
关注公众号，互相学习：钰娘娘知识汇总
