题解 | #最小覆盖子串#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param S string字符串 
 * @param T string字符串 
 * @return string字符串
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
char* minWindow(char* S, char* T ) {
    int left = 0, right = 0;
    int i = 0, j = 0;
    int S_len = strlen(S);
    int T_len = strlen(T);
    int flag = 0;
    int min_l = 0, min_r = S_len, count = 0;    
    int arr[T_len][2];//记录需要的字符和需要的数量
    int char_need[128];//记录各字符的数量
    int need_count;
    for(i = 0; i < 128; i ++)
    {
        *(char_need + i) = 0;
    }
    for(i = 0, j =0; i < T_len; i ++)
    {
        if(*(char_need + (*(T + i))) == 0)
        {
            *(*(arr + (j ++))) = *(T + i);
        }
        *(char_need + (*(T + i))) += 1;
    } 
    for(i = 0; i < j; i ++)
    {
        *(*(arr + i) + 1) = *(char_need + (*(*(arr + i))));
        *(char_need + (*(*(arr + i)))) = 0;

    }
    need_count = j;
    while(left < S_len)
    {
        flag = 0;
        //求出right位置
        while(!flag && right < S_len) 
        {
            *(char_need + (*(S + right))) += 1;
            flag = 1;
            for(i = 0; i < need_count; i ++)
            {
                if(*(char_need + (*(*(arr + i)))) <  *(*(arr + i) + 1))
                {
                    flag = 0;
                }
            }
            if(flag) 
            {
                count ++;
                break;
            }
            right ++;
        }
        //处理left
        if(!flag) break;
        flag = 1;
        while(flag && left < right) 
        {
            *(char_need + (*(S + left))) -= 1;
            flag = 1;
            for(i = 0; i < need_count; i ++)
            {
                if(*(char_need + (*(*(arr + i)))) <  *(*(arr + i) + 1))
                {
                    flag = 0;
                }
            }
            if(!flag) 
            {
                break;
            }
            left ++;
        }
        if(right - left < min_r - min_l)
        {
            min_l = left ;
            min_r = right ;
        } 
        left ++;
        right ++;
    }
    if(count)
    {
        char *ans = (char *)malloc(sizeof(char)*(min_r - min_l + 2));
        for(i = min_l, j = 0; i <= min_r; i ++, j ++)
        {
            *(ans + j) = *(S + i);
        }
         *(ans + j) = '\0';
        return ans;
    }
    else
    {
        return "";
    }
}