LeetCode: 1. 두 수의 문제 풀이 보고서 와 알고리즘 최적화 사고

최근 에 알고리즘 을 되 찾기 시 작 했 고 LeetCode 에서 문 제 를 풀 었 습 니 다.문제 풀이 보고서 와 최적화 사고 도 기록 했다.
제목 링크: 1. 두 수의 합
제목
정수 배열 지정 nums 목표 치 target 와 함께 이 배열 에서 목표 치 를 찾 아 보 세 요. 두 개 정수, 그리고 그들의 배열 아래 표 시 를 되 돌려 줍 니 다.
너 는 모든 입력 이 하나의 답안 에 만 대응 할 것 이 라 고 가정 할 수 있다.그러나 이 배열 의 같은 요 소 를 반복 적 으로 이용 해 서 는 안 된다.
예시:

nums = [2, 7, 11, 15], target = 9

   [0, 1]

제목 의 뜻 은 매우 간단 하 다. 바로 두 개의 수 를 찾 는 것 이다. 이 두 개의 수 를 더 한 값 은 target 과 같다.각 조 의 입력 에 반드시 답 이 있 을 것 을 보증 합 니 다.
문제 풀이 의 사고 방향.
제목 을 보면 그 두 개의 숫자 만 찾 으 면 된다.그러면 먼저 생각 할 수 있 는 것 은 조합 두 개의 수의 합 을 매 거 하 는 것 이다. 그러나 조합 수의 수량 이 매우 많 기 때문에 이 생각 은 그만 둘 수 있다.
두 수의 합 은 target 과 같 으 며, 반대로 한 수 nums[i] 에 대해 서 는 배열 에서 다른 수 nums[j] 를 찾 을 수 있 습 니까?이렇게 하면 우 리 는 단지 하나의 숫자 에 만 관심 을 가지 면 된다.
폭력 매 거
간단 하고 거 칠 며 한 번 의 순환 은 매 거 nums[j] = target - nums[i], 다른 한 번 은 찾 는 데 쓰 인 다 nums[i].
코드:

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        for(int i = 0; i < nums.Length; i ++) {
            int res = target - nums[i];
            for(int j = 0; j < nums.Length; j ++) {
                if(i == j) continue;
                if(res == nums[j]) return new int[] {i, j};
            }
        }
        return new int[] {};
    }
}

실행 시: nums[j] 메모리 소모: 904ms 사용 시 순위: 29.6MB29 개의 사례 가 1 초 가까이 걸 렸 다.순환 보조 변수 만 있 기 때문에 메모리 소 모 는 사실 크 지 않다.시간 소모 순위 가 비교 뒤 를 이 었 다 는 것 은 더 좋 은 해법 이 있다 는 뜻 이기 도 하 다.
공간 교환 시간
이 문제 의 관건 은 어떻게 신속하게 21.29% 를 찾 느 냐 하 는 것 이다. 폭력 은 최 악의 상황 에서 전체 배열 을 찾 고 마지막 에 야 찾 을 수 있다. 시간 복잡 도 는 바로 j 이다.
그러면 여기 서 우 리 는 O(n) 을 이용 하여 매 핑 을 하여 더욱 빠 른 검색 효율 을 얻 을 수 있다.이론 적 으로 디자인 이 좋 은 상황 에서 상수 급 의 복잡 도 를 달성 할 수 있다.
하나의 예: 값 이 크 지 않 은 상황 에서 값 을 배열 로 표시 할 수 있 고 배열 의 값 은 원래 배열 의 아래 표 로 할 수 있다.즉:O(1) 에 대해 존재 한다 x = nums[i].이렇게 하면 대량의 공간 을 희생 한 상황 에서 조회 효율 이 극치 의 상수 급 hash[x] = i 에 이 를 수 있다.
그러나 안 타 깝 게 도 이 문 제 는 이 방법 을 직접 사용 할 수 없 었 다. O(1) 은 배열 이 정의 할 수 있 는 범 위 를 훨씬 넘 었 기 때문이다.컴 파일 할 때 오류 가 발생 하여 메모리 가 넘 칩 니 다.
당분간 int.MaxValue 에 도달 할 방법 이 없 는 이상 실현 O(1) (여기 서 설 을 보류 하고 깃털 코드 를 다 읽 지 못 하면 index 의 취 법 이 뚜렷 한 해시 흔적 을 보고 추측 한 것) 을 사용 하 는 것 을 고려 할 수 있다.
코드:

public class Solution 
{
    public int[] TwoSum(int[] nums, int target) 
    {
        var dic = new Dictionary>();
        for(int i = 0; i < nums.Length; i ++) 
        {
            int num = nums[i];
            int res = target - num;
            if(dic.ContainsKey(res)) 
            {
                return new int[] {i, dic[res][0]};
            } 
            
            if(!dic.ContainsKey(num)) 
            {
                dic.Add(num, new List(){});
                
            }
            
            dic[num].Add(i);
        }
        return new int[] {};
    }
}

실행 시: Dictionary 메모리 소모: 468 ms 사용 시 순위: 30.5MB개 선 된 알고리즘 순 위 는 이전 과 천차만별 로 이미 이전 78.61% 에 이 르 렀 다.
단지 앞의 3 분 의 1 에 이 르 렀 을 뿐 이 알고리즘 은 더욱 최적화 할 수 있다 는 것 을 설명 한다.
조 회 를 더욱 최적화 하 다.
여기 30% 를 사 용 했 지만 여기 Dictionary 는 목록 입 니 다.잘 생각해 보 세 요. 여 기 는 목록 을 저장 할 필요 가 없습니다. 하나의 값 만 저장 하면 됩 니 다. 한 그룹의 답 만 찾 으 면 되 기 때 문 입 니 다!
그 다음으로 두 번 째 판단 을 빼 고 존재 여 부 를 판단 하지 않 고 직접 덮어 쓰 거나 새로 만 들 면 된다.
마지막 으로 역방향 으로 조회 할 수 있 습 니 다. 이전의 수치 에 하나 TValue 가 부족 한 지 확인 할 수 있 습 니 다. 이에 대응 하 는 것 은 바로 차이 입 니 다. 그러면 두 개의 임시 변 수 를 줄 이 고 약간의 공간 을 최적화 할 수 있 습 니 다.
코드:

public class Solution 
{
    Dictionary dic = new Dictionary();
    public int[] TwoSum(int[] nums, int target) 
    {
        if(nums.Length == 2) return new int[] {0, 1};
        dic.Clear();
        for (int i = 0; i < nums.Length; i++)
        {
            if(dic.ContainsKey(nums[i])) return new int[] {dic[nums[i]], i};
            dic[target - nums[i]] = i;
        }
        return new int[] { };
    }
}

실행 시: nums[i] 메모리 소모: 360 ms 사용 시 순위: 30MB개 선 된 알고리즘 은 이전 보다 크게 차이 가 나 지 는 않 았 지만 이 100 여 밀리초 차이 로 순위 가 상위 98.83% 로 올 랐 다.
이 알고리즘 은 아직도 개선 할 수 있 는 부분 이 있 지만 만약 에 깃털 이 아직 검색 의 복잡 도 를 어떻게 더 낮 출 지 생각 이 없다 면 여 기 는 자신 이 더욱 효율 적 인 해시 알고리즘 을 실현 해 야 할 것 이다.
마지막 에 쓰다
오랫동안 알고리즘 을 접 하지 못 해 서 툴 고 생각 도 막 혔 다.여기 서 만약 에 깃털 이 다음 에 더욱 최적화 하 는 데 초보적인 생각 이 있다 면 시간 이 있 으 면 실험 한 후에 문제 풀이 보고 서 를 한 편 더 추가 할 것 이다.

세그먼트 전략 은 데이터 양 이 어느 정도 에 이 르 렀 을 때 더욱 효율 적 인 알고리즘 을 사용 하고 데이터 양 이 시간 에 비해 해시 가 더 오래 걸 릴 수 있 으 므 로 실험 이 필요 합 니 다.대 의 는 여러 알고리즘 의 시간 소모 한도 값 을 찾 아 한도 값 을 이용 하여 전략 선택 을 하 는 것 이다.

스스로 문제 에 대한 효율 적 인 해시 알고리즘 을 실현 한다.