https://leetcode.com/problems/longest-substring-without-repeating-characters/
刚注册 LeetCode 账号准备补习一下算法。我用 Swift 写了一个自认为效率应该还可以的解,提交之后发现仅比 6% 的答案快。结果翻了一下推荐的最优 solution,逻辑和我写的是完全一样的,不知道性能瓶颈在哪里。求解答,谢谢。
我自己写的( Swift ):
class Solution {
func lengthOfLongestSubstring(_ s: String) -> Int {
var result = 0
var map: [Character:Int] = [:]
var start = 0
for i in 0 ..< s.count {
let c = s[s.index(s.startIndex, offsetBy: i)]
if let last = map[c] {
start = max(start, last + 1)
}
result = max(result, i - start + 1)
map[c] = i
}
return result
}
}
LeetCode 推荐的( Java ):
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>(); // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return ans;
}
}
这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。
V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。
V2EX is a community of developers, designers and creative people.