蓝桥杯2020年第十一届省赛真题-子串分值-java

第一次考虑到的方法：

import java.util.*;

public class Main {
	public static void main(String arg[]) {
		Scanner sc=new Scanner(System.in);
		String str=sc.next();
		int sum=0;
		for(int i=0;i<str.length();i++) {
			for(int j=i;j<str.length();j++) {
				String s=str.substring(i,j+1);
				int count=0;
				int[] zimu=new int[26];
				for(int k=0;k<s.length();k++) {
					zimu[((int)s.charAt(k))-97]+=1;					
				}
				for(int k=0;k<zimu.length;k++) {
					if(zimu[k]==1) {
						count++;
					}					
				}
				sum+=count;
			}
		}
		System.out.print(sum);
		sc.close();
	}
}

分析：

时间复杂度为O(n^2)，超时了，时间超限55

暴力解决不了问题只能分析找规律

假设输入值为：befababc

下标：0 1 2 3 4 5 6 7

元素：b e f a b a b c

子串：befaba

下标：0 1 2 3 4 5

元素：b e f a b a

假如我们要求下标为3的元素a，在其可能包含a的子串中，出现一次的子串有多少个。出现一次，那么就碰到前后为a的时候停止，直到结束。如下：

往左找

a

fa

efa

befa

往右找

ab

左右两边并起来

fab

efab

befab

总共8个子串符合要求，我们可以发现总子串数=左子串数*（右子串数+1）

再结合下标来求公式，上面例子：（3- （-1））（5-3），下标为i推出公式为（i - left）（right - i）

left和right分别是左右碰到a或者结束的时候的下标

通过上面找规律，是不是发现可以用一个循环把字符串都遍历完，我们只需要将每一个元素含有多少个符合包含该元素且只出现一次的子串，然后将所有元素的符合子串个数相加，就可以了。

代码：

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {        
    	Scanner sc=new Scanner(System.in);
		String str=sc.next();
		int len=str.length();
		int right,left,sum=0;
		
		for(int i=0;i<len;i++){
			for(right=i+1;right<len;right++){
				if(str.charAt(right)==str.charAt(i)){					
					break;
				}
			}
			for(left=i-1;left>=0;left--){
				if(str.charAt(left)==str.charAt(i)){
					break;
				}
			}
			sum += (i-left)*(right-i);
		}
		System.out.print(sum);
		sc.close();
    }
}