求kdb实现无重复字符最长子串方案及scan函数条件终止方法

问题1：实现无重复字符的最长子串 #

用滑动窗口+哈希表的思路，时间复杂度O(n)，每个字符仅遍历一次，哈希表快速追踪字符最新位置来调整窗口边界。

代码实现 #

longestSubstring:{[s]
    // 用scan累积窗口状态：(窗口起始位置, 当前最长长度, 字符位置映射表)
    max last scan[{[state; ic]
        i: ic[0]; c: ic[1];
        start: state[0]; maxLen: state[1]; pos: state[2];
        // 若当前字符在窗口内已存在，更新窗口起始位置
        newStart: $[c in key pos; max start 1+pos[c]; start];
        // 更新当前字符的最新位置
        newPos: pos[c]::i;
        // 计算当前窗口长度并更新最大值
        newMaxLen: max maxLen i - newStart + 1;
        (newStart; newMaxLen; newPos)
    }] (0; 0; ()) enumerate s
}

测试示例 #

q)longestSubstring "abcabcbb"
3
q)longestSubstring "bbbbb"
1
q)longestSubstring "pwwkew"
3

问题2：让迭代在满足条件时停止（斐波那契例子） #

kdb的scan是固定次数迭代，要实现条件终止，用while循环最直接，也可以用递归。

循环实现（推荐） #

fibUntilSum:{[limit]
    res: 1 1;
    // 当当前序列和未超过限制时，继续添加下一个斐波那契数
    while[sum res <= limit; res,: sum -2#res];
    // 若最后一次添加导致和超限，移除最后一个元素
    $[sum res > limit; -1#res; res]
}

递归实现 #

fibRecur:{[res; limit]
    $[sum res > limit; -1#res; .z.s[res,: sum -2#res; limit]]
}
// 调用方式
q)fibRecur[1 1; 100]
1 1 2 3 5 8 13 21 34

测试示例 #

q)fibUntilSum 100
1 1 2 3 5 8 13 21 34

内容的提问来源于stack exchange，提问作者Rezzy