Ref: https://leetcode-cn.com/leetbook/read/sliding-window-and-two-pointers/owu6dt/

循环不变量

「循环不变量」是指我们在编写代码的过程中，要一直循序不变的性质，这样的性质是根据要解决的问题，由我们自己定义的。「循环不变量」是我们写对一个问题的基础，保证了在「初始化」「循环遍历」「结束」这三个阶段相同的性质，使得一个问题能够被正确解决。

题目

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

思路分析：这个问题并不难，相信大家一定可以独立做出来。我们给出两种写法，两种写法里 i 都是用于遍历的下标，而 j 的含义不同，请大家分别比较两者代码的差异。

定义：j 指向马上要赋值的元素的下标，因此我们定义区间 [0..j) （注意是左闭右开区间，j 不能取到）里没有重复元素。pre 永远指向第 1 个不重复的数字；

  • 初始化：为了保证区间 [0..j) （注意这里是左闭右开区间）里没有重复元素。初始的时候，i = 0 ，下标为 0 的位置只有一个数，区间 [0..j) 一定不会出现重复，这件事情表示为区间 [0..0] 没有重复数字，即区间 [0..1) 没有重复数字，因此 j 初始化的时候需要等于 1；
  • 保持：遇到和 pre 指向的数字相等元素，i++ 直接看到下一个元素，如果 nums[i] != pre ，表示程序看到了第 1 个不重复的数字，此时需要赋值 nums[j] = nums[i] 和 pre = nums[j] ，然后让 j++ 指向下一个需要赋值的下标；

  • 终止：循环结束以后 i = len ，程序看完了输入数组的所有元素，此时区间 [0..j) 里没有重复元素，它的长度为 j ，返回 j。

    1. public class Solution {
    3.   public int removeDuplicates(int[] nums) {
    4.       int len = nums.length;
    5.       if (len < 2) {
    6.           return len;
    7.       }
    8.       int j = 0;
    9.       for (int i = 1; i < len; i++) {
    10.           if (nums[i] != nums[j]) {
    11.               j++;
    12.               nums[j] = nums[i];
    13.           }
    14.       }
    15.       return j + 1;
    16.   }
    17. }

2.经典场景

不重复字串最大长度

Ref: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

  1. class Solution {
  2.     public int lengthOfLongestSubstring(String s) {
  3.         // 哈希集合，记录每个字符是否出现过
  4.         Set<Character> occ = new HashSet<Character>();
  5.         int n = s.length();
  6.         // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
  7.         int rk = -1, ans = 0;
  8.         for (int i = 0; i < n; ++i) {
  9.             if (i != 0) {
  10.                 // 左指针向右移动一格，移除一个字符
  11.                 occ.remove(s.charAt(i - 1));
  12.             }
  13.             while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
  14.                 // 不断地移动右指针
  15.                 occ.add(s.charAt(rk + 1));
  16.                 ++rk;
  17.             }
  18.             // 第 i 到 rk 个字符是一个极长的无重复字符子串
  19.             ans = Math.max(ans, rk - i + 1);
  20.         }
  21.         return ans;
  22.     }
  23. }