java基础-双指针算法

小伙伴们，你们好呀！我是老寇！

双指针算法是基于暴力解法的优化，将时间复杂度降低到线性。

双指针算法与其说是一种算法，不如说是一种技巧，它能够缩短循环遍历的时间，提高程序的运行速度！

双指针分为两类，快慢指针和左右指针：

1.快慢指针（弗洛伊德循环查找算法），类似龟兔赛跑。

2.左右指针又称指针碰撞，就是一左一右遍历。

注：多练习，印象才更深刻

快慢指针

<a href="https://leetcode-cn.com/problems/happy-number/" title="快乐数">快乐数</a>

class Solution {
   public boolean isHappy(int n) {
     int slow = n,fast = n;
     do{
      slow = bitSquareSum(slow);
      fast = bitSquareSum(fast);
      fast = bitSquareSum(fast);
     }
     while(slow != fast);
     return (slow == 1);
   }

   private int bitSquareSum(int x) {
     int sum = 0,cur;
     while(x > 0) {
      cur = x % 10;
      x = x / 10;
      sum += cur * cur;
     }
     return sum;
   }
}

结论：较哈希集，指针只需要常数的额外空间

<a class="link-info" href="https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/" title="删除有序数组中的重复项">删除有序数组中的重复项</a>

class Solution {
   public int removeDuplicates(int[] nums) {
     int len = nums.length;
     if(len < 2) {
      return len;
     }
     int j = 0;
     for(int i = 0; i < len; i++) {
      if(nums[j] != nums[i]) {
        nums[++j] = nums[i];
      }
     }
     return j + 1;
   }
}

结论：找对「循环不变量」是做题的关键，我理解的循环遍历是一个if条件，在本题中nums[j]是慢指针，负责数据的替换，nums[i]是快指针，负责数据的遍历。

左右指针

<a href="https://leetcode-cn.com/problems/reverse-string/" title="反转字符串">反转字符串</a>

class Solution {
   public void reverseString(char[] s) {
     int left = 0,right = s.length - 1;
     char c;
     while(left < right) {
      c = s[left];
      s[left] = s[right];
      s[right] = c;
      left++;right--;
     }
   }
}

结论：较套用两层for循环，所要的时间快一点

双指针范式（作者总结）

//举栗子 数组n1,n2
//1.排序
Arrays.sort(n1);
Arrays.sort(n2);
//数组索引从0开始
int index = 0,index1 = 0,index2 = 0;
//开辟数组
int len1 = n1.length,len2 = n2.length;
int[] arr = new int[Math.min(n1,n2)];
//指针动起来
while(index1 < len1 &amp;&amp; index2 < len2) {
   if(两个值相等) {
     index1++;
     index2++;
     arr[index++] = 其中一个值
   } else if (第一个值大) {
    index2++;
   } else {
    //第二个值大
    index1++;
   }
}

//谁小谁加+1

原文地址：https://blog.csdn.net/qq_39893313/article/details/120147123?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522168904460816782427413519%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=168904460816782427413519&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-9-120147123-null-null.142^v88^control_2,239^v2^insert_chatgpt&utm_term=java%E4%BC%98%E5%8C%96