数组中两个字符串的最小距离

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] data=br.readLine().split(" ");
        String str1=data[0];
        String str2=data[1];
        String[]strs=new String[n];
       for (int i = 0; i <n; i++) {
            strs[i]=br.readLine();
        }
            int res = minDistance(strs, str1, str2);
            System.out.println(res);
        }
    
    public static int minDistance(String[]strs,String str1,String str2){
        if(str1==null||str2==null){
            return -1;
        }
        if(str1.equals(str2)){
            return 0;
        }
        int last1=-1;
        int last2=-1;
        int min=Integer.MAX_VALUE;
        for(int i=0; i<strs.length; i++){
            if(strs[i].equals(str1)){
                min=Math.min(min,last2==-1?min:i-last2);
                last1=i;
            }
            if(strs[i].equals(str2)){
                min=Math.min(min,last1==-1?min:i-last1);
                last2=i;
            }
        }
        return min==Integer.MAX_VALUE?-1:min;
    }
 }

O(N)的时间复杂度，从左往右扫一遍，空间复杂度O(1)

扫到了记录last1和last2分别表示str1和str2最近出现的下标，那么i - last1或i - last2就是最短的距离，一直更新这个最短距离。

import java.util.*;

public class Main {
    public static int process(String[] strs, String str1, String str2) {
        if (str1 == null || str2 == null) {
            return -1;
        }
        int last1 = -1, last2 = -1, min = Integer.MAX_VALUE;
        for (int i = 0; i < strs.length; i++) {
            if (strs[i].equals(str1)) {
                min = last2 == -1 ? min : Math.min(min, i - last2);
                last1 = i;
            } else if (strs[i].equals(str2)) {
                min = last1 == -1 ? min : Math.min(min, i - last1);
                last2 = i;
            }
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String str1 = sc.next();
        String str2 = sc.next();
        String[] strs = new String[n];
        for (int i = 0; i < n; i ++) {
            strs[i] = sc.next();
        }
        sc.close();
        int res = process(strs, str1, str2);
        System.out.println(res);
    }
}