java基础-双指针算法

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

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

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

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

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

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

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

快慢指针

快乐数

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;
    }
}

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

删除有序数组中的重复项

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]是快指针，负责数据的遍历。

左右指针

反转字符串

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 && index2 < len2) {
   if(两个值相等) {
      index1++;
      index2++;
      arr[index++] = 其中一个值
   } else if (第一个值大) {
     index2++;
   } else {
     //第二个值大
     index1++;
    }
}

//谁小谁加+1