3.18

使用滑动窗口法即可解决，关键在于如何确定如何修改窗口边界

具体代码如下:

#include <stdio.h>
#include <string.h>

int max(int a,int b){
    return a>b?a:b;
}

int lengthOfLongestSubstring(char* s) {
 int char_index[128];
    memset(char_index, -1, sizeof(char_index)); // 初始化为 -1
    // 初始化滑动窗口的左边界
    int left = 0;
    // 初始化最长子串的长度
    int max_length = 0;	
    
    for (int right = 0; s[right] != '\0'; right++) {
        // 如果字符已经在数组中，并且它的索引大于等于左边界，更新左边界
        if (char_index[s[right]] >= left) {
            left = char_index[s[right]] + 1;
        }
        // 更新字符的索引
        char_index[s[right]] = right;
        // 更新最长子串的长度
        max_length = (right - left + 1) > max_length ? (right - left + 1) : max_length;
    }

    return max_length;
}

这段代码实现了求解给定字符串 s 中不含重复字符的最长子串的长度。让我详细解释一下它的思路：

滑动窗口：这个算法使用了滑动窗口的思想。滑动窗口是一个固定大小的窗口，可以在字符串上滑动，以便处理连续的子串。
字符索引数组：代码中定义了一个名为 char_index 的整数数组，用于存储每个字符在字符串中的最新索引位置。初始时，所有元素都被设置为 -1。
左指针和右指针：我们使用两个指针 left 和 right 来构建滑动窗口。初始时，left 和 right 都指向字符串的开头。
遍历字符串：我们遍历字符串 s，从左到右，处理每个字符。
更新左指针：
如果字符 s[right] 已经在 char_index 数组中，并且它的索引大于等于 left，说明窗口内有重复字符。
此时，我们将 left 更新为 char_index[s[right]] + 1，即将左指针移动到重复字符的下一个位置，以消除重复。
更新字符索引：将 char_index[s[right]] 更新为 right，表示字符 s[right] 最新出现的位置。
更新最长子串长度：计算当前窗口的长度 (right - left + 1)，并将其与 max_length 比较，取较大值作为最长子串的长度。
右指针右移：将右指针 right 向右移动一位，继续处理下一个字符。
返回最长子串长度：最终返回 max_length，即不含重复字符的最长子串的长度。
这样，代码通过维护一个滑动窗口和字符索引数组，有效地找到了不含重复字符的最长子串的长度。

该代码值得学习的是用s[right]是否等于'\0'来判断是否到了数组末尾,避免了使用strlen计算数组的长度,然后使用?:来比较大小,省去了写max函数

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 函数功能：在字符串 s 中查找所有可以由 words 数组中的单词串联形成的子串的起始位置
// 参数说明：
//   s: 输入的字符串
//   words: 字符串数组，存储要匹配的单词
//   wordsSize: words 数组中单词的数量
//   returnSize: 输出参数，存储结果数组的大小
// 返回值：指向存储结果的整数数组的指针
int* findSubstring(char * s, char ** words, int wordsSize, int* returnSize) {
    *returnSize = 0;
    if (wordsSize == 0) return NULL;

    int one_word_len = strlen(words[0]);
    int word_num = wordsSize;
    int all_len = one_word_len * word_num;
    int s_len = strlen(s);

    if (s_len < all_len) return NULL;

    char temp[one_word_len + 1]; // 临时存储截取的子串
    int *local = (int *)malloc(sizeof(int) * s_len); // 存储结果的整数数组
    int flag[wordsSize]; // 标记单词是否被查到
    int i = 0, j, res, k;

    while (i + all_len <= s_len) {
        for (int m = 0; m < wordsSize; m++) flag[m] = 0;

        // 通过滑动窗口的方式截取长度为 wordLen * wordsCount 的子串
        for (j = i; j < i + all_len; j += one_word_len) {
            strncpy(temp, s + j, one_word_len);
            temp[one_word_len] = '\0'; // 注意：将字符数组末尾设置为 '\0'

            res = 0; // 标记该单词在 words 中是否被查到
            for (k = 0; k < wordsSize; k++) {
                if (flag[k] == 1) continue;
                if (strcmp(temp, words[k]) == 0) {
                    flag[k] = 1;
                    res = 1;
                    break;//找到了
                }
            }
-.3
    31
            if (res == 0) break;//没找到
        }

        if (res == 1) {
            local[(*returnSize)++] = i; // 将子串的起始索引保存到结果数组中
        }

        i++;
    }

    return local;
}

int main() {
    char s[] = "barfoothefoobarman";
    char *words[] = {"foo", "bar"};
    int wordsSize = 2;
    int returnSize;
    int *result = findSubstring(s, words, wordsSize, &returnSize);

    printf("Result: ");
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", result[i]);
    }

    return 0;
}