10 双指针：如何掌握最长、定长、最短区间问题的解题决窍？

1

int[] A = new int{1,2,3,4};

1
2
3

[1, 2, 3]
   [2, 3]
      [3]

1
2
3
4

i = 0, A[0] = 1 => [1]
i = 1, A[1] = 2 => [1, 2], [2]
i = 2, A[2] = 3 => [1, 2, 3], [2, 3], [3]
i = 3, A[3] = 4 => [1, 2, 3, 4], [2, 3, 4], [3, 4], [4]

1
2
3
4
5
6
7
8

step1. 将A[i]加到区间中，形成新区间(left, i]

// 遍历A[i]的区间右端固定集合，直找到以A[i]为右端点的最优解
step2. while (left < i && (left,i]区间不满足要求) {
  left++;
}
// 此时要么得到一个满足要求的
step 3. (left, i]区间满足要求

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

int maxLength(int[] A) {
  int N = A.length;
  // 区间的左指针
  int left = -1;
  int ans = 0;
  for (int i = 0; i < N; i++) {
    // assert 在加入A[i]之前，(left, i-1]是一个合法有效的区间
    // step 1. 直接将A[i]加到区间中，形成(left, i]
    // step 2. 将A[i]加入之后，惰性原则
    while (check((left, i]))/*TODO 检查区间状态是否满足条件*/) {
      ++left; // 如果不满足条件，移动左指针
      // TODO 修改区间的状态
    }
    // assert 此时(left, i]必然满足条件
    ans = max(ans, i - left);
  }
  return ans; // 返回最优解
}

1

while (check((left, i]))是否满足条件)

1
2
3
4
5

// pos[]数组用来记录每个字符的位置
while (left < i && pos[字符] > left) {
  // 然后移动left
  // TODO 修改区间状态
}

1
2
3
4
5

// pos[]数组用来记录每个字符的位置
while (left < i && pos[字符] > left) {
  // 然后移动left
  left = pos[字符];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

int lengthOfLongestSubstring(String s) {
  final int N = s == null ? 0 : s.length();
  int[] pos = new int[256];
  Arrays.fill(pos, -1);
  int ans = 0;
  int left = -1;
  for (int i = 0; i < N; i++) {
    final int idx = (int)s.charAt(i);
    // (left, i)已经是一个有效的解
    // 现在要把s[i]加进来
    // 1. 坏了才移动
    // 那么看一下是否会坏？
    while (pos[idx] > left) {
      // 如果(left, i)里面已经有了s[i]
      // 那么需要移动左边，
      // 移动的时候，怎么移动？
      // 可以直接将left 移动到pos[s[i]]
      // 因为我们采用的区间是左开右闭
      left = pos[idx];
    }
    pos[idx] = i;
    ans = Math.max(ans, i - left);
  }
  return ans;
}

1
2
3
4
5
6

A[3] = 2:
[100, 1, 1, 1, 2]
     [1, 1, 1, 2] <-- 最优解：乘积 < 6的最长区间
        [1, 1, 2]
           [1, 2]
              [2]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

int rangeCounter(int[] A) {
  int N = A.length;
  // 区间的左指针
  int left = -1;
  int ans = 0;
  // 不变式0: 最开始的区间为(-1, -1] 是一个空区间
  //         我们认为空区间总是满足条件!
  for (int i = 0; i < N; i++) {
    // 不变式1: 在加入A[i]之前，(left, i-1]是一个合法有效的区间
    // step 1. 直接将A[i]加到区间中，形成(left, i]
    // step 2. 将A[i]加入之后，惰性原则
    while (check((left, i]))/*TODO 检查区间状态是否满足条件*/) {
      ++left; // 如果不满足条件，移动左指针
      // TODO 修改区间的状态
    }
    // 不变式2：此时(left, i]必然合法
    // 累计区间个数
    ans += i - left;
  }
  return ans; // 返回最优解
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

int numSubarrayProductLessThanK(int[] A, int k) {
  final int N = A == null ? 0 : A.length;
  int left = -1;
  long ans = 0;
  long s = 1;
  for (int i = 0; i < N; i++) {
    long x = A[i];
    // 将x加到子数组中
    s *= x;
    // 如果破坏了约束，那么移动左指针
    while (s >= k && left < i) {
      s /= A[++left];
    }
    // 此时必然满足要求
    ans += i - left;
  }
  return (int)ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

int fixedLength(int[] A, int windowSize) {
  final int N = A == null ? 0 : A.length;
  int left = -1;
  for (int i = 0; i < N; i++) {
    // step 1. 直接将A[i]加到区间中，形成(left, i]
    // TODO 修改区间的状态
    // 如果滑动窗口还太小
    if (i - left < windowSize) {
      continue;
    }
    // assert 此时(left, i]长度必然等于windowSize
    // TODO 判断区间的状态是否满足约束条件
    left++;
    // step 2. 移除A[left]
    // TODO 修改区间状态
  }
  return ans; // 返回最优解
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

boolean checkInclusion(String A, String B) {
  // B contains A的任意排列？
  final int blen = B == null ? 0 : B.length();
  final int alen = A == null ? 0 : A.length();
  // 统计A字符串里面各个字符的出现次数
  int[] astat = new int[256];
  for (int i = 0; i < alen; i++) {
    astat[A.charAt(i)]++;
  }
  // 统计B字符串里面的子串的字符的出现次数
  int[] bstat = new int[256];
  // 滑动窗口的左边起始点，我们使用(left, i]来表示这个
  // 定长区间
  int left = -1;
  for (int i = 0; i < blen; i++) {
    // step 1. 直接将A[i]加到区间中，形成(left, i]
    // DONE 修改区间的状态
    Character c = B.charAt(i);
    bstat[c]++;
    // 如果窗口还太小，此时不满足定长的条件
    if (i - left < alen) {
      continue;
    }
    // assert 此时(left, i]长度必然等于windowSize
    // DONE 判断区间的状态是否满足约束
    boolean same = true;
    for (int j = 0; j < 256 && same; j++) {
      same = astat[j] == bstat[j];
    }
    if (same)
      return true;
    // 移除滑动窗口的尾巴!
    left++;
    bstat[B.charAt(left)]--;
  }
  return false;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

// 统计类
class Counter extends astatashMap<Character, Integer> {
  public int get(Character k) {
    return containsKey(k) ? super.get(k) : 0;
  }
  public void add(Character k, int v) {
    put(k, get(k) + v);
    if (get(k) <= 0) {
      remove(k);
    }
  }
}
boolean checkInclusion(String A, String B) {
  // B contains A?
  final int blen = B == null ? 0 : B.length();
  final int alen = A == null ? 0 : A.length();
  // 统计A字符串里面每个字符的出现次数。
  Counter astat = new Counter();
  for (int i = 0; i < alen; i++) {
    astat.add(A.charAt(i), 1);
  }
  // 统计B字符串里面每个字符的出现次数。
  Counter bstat = new Counter();
  int left = -1;
  // 比较bstat与astat，有多少个字符的统计结果已经是相等的。
  int equal = 0;
  for (int i = 0; i < blen; i++) {
    // 将B[i]添加到区间中
    Character c = B.charAt(i);
    // 更新区间的状态
    bstat.add(c, 1);
    // 更新两个计数器相等的计数项的个数
    if (bstat.get(c) == astat.get(c)) {
      equal++;
    }
    // 如果窗口太小
    if (i - left < alen) {
      continue;
    }
    // assert 此时(left, i]长度必然等于windowSize
    // DONE 判断区间的状态是否满足约
    if (equal == astat.size()) {
      return true;
    }
    // 移除滑动窗口的尾巴!
    left++;
    // 更新移动后的区间的状态
    Character rm = B.charAt(left);
    if (bstat.get(rm) == astat.get(rm)) {
      equal--;
    }
    bstat.add(rm, -1);
  }
  return false;
}

1
2
3
4
5
6
7
8
9

for (int start = 0; start < L; start++) {
  // 这里开始遍历
  // 数组0. ["AA", "BB", "CC", "BB", "AA"]
  // 数组1. ["AB", "BC", "CB", "BA"]
  for (int i = start; i + L <= s.length(); i+= L) {
    String tmp = s.substring(i, i + L);
    // tmp就是依次取出数组中的单词。
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

class Counter extends HashMap<String, Integer> {
  public int get(String k) {
    return containsKey(k) ? super.get(k) : 0;
  }
  public void add(String k, int v) {
    put(k, get(k) + v);
    if (get(k) <= 0) {
      remove(k);
    }
  }
}
List<Integer> findSubstring(String s, String[] D) {
  Counter H = new Counter();
  int wordLength = 0;
  // 统计字典中单词出现的次数
  for (String w : D) {
    wordLength = w.length();
    H.add(w, 1);
  }
  List<Integer> ans = new ArrayList<>();
  for (int start = 0; start < wordLength; start++) {
    // 切分点从start开始，相当于我们得到了一个新的数组。
    Counter R = new Counter();
    int left = start - wordLength;
    int equalCount = 0;
    // 有效的区间是(left, i]
    int counter = 0;
    for (int i = start; i + wordLength <= s.length();
            i += wordLength) {
      // 依次取出数组中的单词。
      String tmp = s.substring(i, i + wordLength);
      R.add(tmp, 1);
      if (R.get(tmp) == H.get(tmp)) {
        equalCount++;
      }
      counter++;
      // 如果窗口太小
      if (counter < D.length) {
        continue;
      }
      // 到这里时，窗口的长度已经一样了
      // 看一下命中率
      if (equalCount == H.size()) {
        ans.add(left + wordLength);
      }
      // 移除开头的那个元素
      left += wordLength;
      String rm = s.substring(left, left + wordLength);
      if (R.get(rm) == H.get(rm)) {
        equalCount--;
      }
      R.add(rm, -1);
    }
  }
  return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

int minimalRange(int[] A) {
  final int N = A == null ? 0 : A.length;
  // 子串的左边，采用左开右闭原则(left, i]表示一个子串
  int left = -1;
  // 记录最短的子串的长度
  int ans = A.length + 1;
  for (int i = 0; i < N; i++) {
    // 注意 在加入A[i]之前，(left, i-1]可能不满足条件!
    // step 1. 直接将A[i]加到区间中，形成(left, i]
    // step 2. TODO 更新区间的状态
    while (区间超出/满足条件) {
      ans = Math.min(ans, i - left);
      // step 3. 移除A[++left];
      // step 4. TODO 更新区间的状态
    }
    // assert ! 区间(left, i]到这里肯定不满足条件
  }
  return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

String minWindow(String A, String B) {
  // A 中包含B中所有字符的最短子串。
  // 两个字符串的长度。
  final int alen = A == null ? 0 : A.length();
  final int blen = B == null ? 0 : B.length();
  // 统计B字符串里面字符出现的次数
  int[] bstat = new int[256];
  // items表示B字符串里面出现的字符的种类。类似于hash.size();
  int items = 0;
  for (int i = 0; i < blen; i++) {
    bstat[B.charAt(i)]++;
    if (bstat[B.charAt(i)] == 1) {
      items++;
    }
  }
  // 开始使用最短区间的模板
  int left = -1;
  int ans = alen + 1;
  int start = 0;
  // 用来记录子串里面字符出现的次数
  int[] astat = new int[256];
  // 用来判断两个哈希表中已经有多少项相等了。
  int equal = 0;
  for (int i = 0; i < alen; i++) {
    astat[A.charAt(i)]++;
    if (astat[A.charAt(i)] == bstat[A.charAt(i)]) {
      equal++;
    }
    // 积极原则，最短区间要主动破坏条件
    while (equal >= items) {
      // 更新最优解
      if (ans > i - left) {
        start = left + 1;
        ans = i - left;
      }
      // 移除最左端的元素，并且更新区间的状态
      ++left;
      if (astat[A.charAt(left)] == bstat[A.charAt(left)]) {
        equal--;
      }
      astat[A.charAt(left)]--;
    }
  }
  return ans <= alen ? 
    A.substring(start, start + ans) : new String("");
}