使用两点法的直觉

Question

我正在 LeetCode.com 上解决一个问题：

A string S of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.
For the input: "ababcbacadefegdehijhklij" the output is: [9,7,8]

一个highly upvoted solution如下：

public List<Integer> partitionLabels(String S) {
    if(S == null || S.length() == 0){
        return null;
    }
    List<Integer> list = new ArrayList<>();
    int[] map = new int[26];  // record the last index of the each char

    for(int i = 0; i < S.length(); i++){
        map[S.charAt(i)-'a'] = i;
    }
    // record the end index of the current sub string
    int last = 0;
    int start = 0;
    for(int i = 0; i < S.length(); i++){
        last = Math.max(last, map[S.charAt(i)-'a']);
        if(last == i){
            list.add(last - start + 1);
            start = last + 1;
        }
    }
    return list;
}

我明白我们在第一个 for 循环中做了什么（我们只是存储了最后一次出现的字符的索引），但我不太确定第二个：

一个。为什么要计算max()和比较last==i？
b.它如何帮助我们实现我们所寻求的 - 在上面的示例中，当我们在位置 8（0 索引）处遇到 a 时，是什么保证我们不会遇到，比如说 b，在大于8的位置？因为，如果我们这样做，那么将 8 视为我们子字符串的结束位置是不正确的。

谢谢！

Answer 1

如果我们遇到一个字符 S[i]，我们可能只会在它最后一次出现后才切断字符串，因此 map[S.charAt(i)-'a']。我们最大化 last 中的值，因为我们需要确保所有处理过的字符最后一次出现在前缀中，因此我们查看此类索引的最右边，因此是 max。如果我们遇到一个字符 S[i] 使得 i 是它的最后一次出现并且之前的所有字符的最后一次出现都在 i 之前，我们可以将子字符串 start..i 添加到结果中，并为下一个子字符串设置 start = i + 1。

Answer 2

思路是这样的。每当特定字符的最后一次出现与当前索引匹配时，就意味着该特定字符仅出现在该部分。

为了更好地理解这一点，就这样做吧。

int last = 0;
int start = 0;
for(int i = 0; i < S.length(); i++){
   last = Math.max(last, map[S.charAt(i)-'a']);
   System.out.println(last+" "+i);
   if(last == i){
      list.add(last - start + 1);
      start = last + 1;
   }
}

以您的示例字符串为例 "ababcbacadefegdehijhklij"。

现在，输出将是

a 的最后一次出现在第 8 个位置。现在我们处于第 0 位。增量 i。所以，直到我们到达第 8 个位置，我们不能确定每个部分最多包含 1 个字符。假设下一个字符是b，最后出现在第10位，那么我们需要确认到第10位。

if(last == i){

}

以上if只是确认该部分已经结束，我们可以从下一个索引开始新的部分。在这样做之前，我们将当前部分的长度添加到输出中。

使用两点法的直觉

Intuition behind using a two pointers approach

java

algorithm

logic