leetcode 3 중복 문자 없 는 최 장 하위 문자열 (C \ #)

제목.
문자열 을 지정 합 니 다. 중복 문자 가 없 는 가장 긴 문자열 의 길 이 를 찾 아 보 세 요.
예제 1: 입력: "abcabcbb" 출력: 3 설명: 중복 문자 가 없 는 가장 긴 문자열 은 "abc" 이기 때문에 길 이 는 3 입 니 다.
예시 2: 입력: "bbbbb" 출력: 1 설명: 중복 문자 가 없 는 가장 긴 문자열 은 "b" 이기 때문에 길이 가 1 입 니 다.
예시 3: 입력: "pwkew" 출력: 3 설명: 중복 문자 가 없 는 가장 긴 문자열 은 "wke" 이기 때문에 길이 가 3 입 니 다.당신 의 답 은 반드시 하위 문자열 의 길이 여야 합 니 다. "Pwke" 는 하위 서열 이지 하위 문자열 이 아 닙 니 다.
문제 풀이:
제목 설명 에서 힌트 를 주 었 습 니 다. 우리 가 찾 아야 할 가장 긴 문자열 은 이 문자열 의 모든 문자 가 위치 에 있어 야 한 다 는 뜻 입 니 다.
해법 1: 폭력 해법 은 현재 판단 중인 문자열 을 string 으로 저장 합 니 다. 새 문 자 를 추가 할 때마다 이 문자열 에 존재 하 는 지 여 부 를 옮 겨 다 니 며 존재 하면 이 문자열 을 List 에 직접 되 돌려 주 고 존재 하지 않 으 면 이 문 자 를 추가 합 니 다.마지막 으로 List 를 옮 겨 다 니 며 가장 긴 문자열 을 찾 습 니 다.그러나 이 방법 은 운행 시간 이 초과 되 어 버 릴 수 밖 에 없다.
해법 2: 슬라이딩 창 1. 두 개의 플래그 비트 start 와 end 를 설정 합 니 다. 초기 값 은 0 이 고 string 의 첫 번 째 문 자 를 가리 키 는 것 을 의미 합 니 다.2. hash 표를 만 들 고 key 에 문 자 를 저장 합 니 다. value 는 문자열 에 있 는 위치 + 1 (+ 1) 을 저장 합 니 다. 검 측 된 문자 가 이 문자 와 같 으 면 새 문자 가 중복 되 지 않 으 려 면 앞에서 중복 되 는 문 자 를 제거 해 야 합 니 다. 새 문자열 의 시작 위 치 는 이 문자 가 문자열 에 있 는 위치 + 1, 즉 value 값 입 니 다.이 부분 은 스스로 그림 을 그 려 서 좀 이해 할 것 을 건의 합 니 다.쉽게 말 하면 이 hash 표 에 저 장 된 정 보 는 * * (문자 a, a 중복 시 새 문자열 의 시작 위치) * * 입 니 다.
두 가지 예: [1] 중복 문자 가 인접 해 있 습 니 다. 문자열 "abba" 는 세 번 째 문자 가 검출 되 었 을 때 중복 되 어야 합 니 다. 새로운 문자열 은 세 번 째 문자 부터 중복 되 지 않 습 니 다. [2] 중복 문자 가 인접 하지 않 습 니 다. 문자열 "dvdf" 는 세 번 째 문자 가 검출 되 었 을 때 중복 되 어야 합 니 다. 그러면 새 문자열 은 두 번 째 문자 부터 중복 되 지 않 습 니 다.
3. end 가 계속 증가 하고 start 는 중복 문자 가 나타 날 때 만 변 합 니 다. 가장 긴 문자열 의 길 이 는 (end - start + 1) 로 계산 합 니 다.
주의해 야 할 점: start 값 이 바 뀌 었 을 때 현재 start 의 값 과 목표 값 을 비교 해 야 합 니 다. "abba" 문자열 과 같은 경우 "ba" 로 판단 하기 때 문 입 니 다.이때 start 는 b 를 가리 키 고 end 는 a 를 가리 키 며 a 는 hash 표 에 저 장 됩 니 다. value 는 1 입 니 다. start 에 직접 value 값 을 부여 하면 새 문자열 은 첫 번 째 a 부터 시작 할 수 없습니다. 그래서 * * start = Math. Max (int) hs [s [end], start) 를 비교 합 니 다. * * 이 문 구 는 상기 상황 을 방지 합 니 다.(예전 에 비교 하지 않 아서 제 결과 가 틀 렸 습 니 다. 한 마디 한 마디 실 수 를 하고 나 서 야 실 수 를 발 견 했 습 니 다. f11 은 필요 합 니 다)

//C#  
public class Solution {
    public int LengthOfLongestSubstring(string s) {
        Hashtable hs = new Hashtable();
            int n = s.Length;
            int ans = 0;
            int start = 0;
            for (int end = 0; end < n; end++)
            {
                if (hs.ContainsKey(s[end]))
                {
                     start =Math.Max((int)hs[s[end]],start);
                     hs[s[end]]=end+1;
                }
                else hs.Add(s[end], end + 1);
                ans = Math.Max(end - start + 1, ans);
            }
            return ans;
    }
}

사고방식 과 코드 는 이 사내 아 이 를 참고 했다.https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-jie-suan-fa-3-wu-zhong-fu-zi-fu-de-zui-chang-z/