>

이 문제 를 해결하려고합니다 :

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

이것은 나의 구현이다 :

public int[] twoSum(int[] numbers, int target) {
    Map<Integer, Integer> numbersMap = new HashMap<Integer, Integer>();
    int[] requiredNumbers = null;
    int index = 0;
    for (int number : numbers) {
        if (numbersMap.containsKey(target - number)) {
            requiredNumbers = new int[2];
            requiredNumbers[0] = numbersMap.get(target - number);
            requiredNumbers[1] = index;
            return requiredNumbers;
        } else {
            numbersMap.put(number, index);
            index++;
        }
    }
    return requiredNumbers;
}

실행 시간을 어떻게 개선 할 수 있습니까?


  • 답변 # 1

    입력 배열의 크기가경우, HashMap 의 용량을 미리 할당하여 속도를 높일 수 있습니다 :

    Map<Integer, Integer> numbersMap = new HashMap<Integer, Integer>(numbers.length * 2);
    
    
    알고리즘이 실행됨에 따라 데이터가 HashMap 에 추가됩니다. . 출품작 수가 capacity * load_factor 를 초과하는 경우 해시 맵의 용량이 두 배가되고 더 큰 용량을 위해 요소가 리 바인드됩니다. 이 용량 배가 및 리 바인딩에는 시간이 걸립니다. 자주 발생하지는 않지만\ $O (\ log N) \ $번이지만 충분한 용량의 해시 맵으로 시작하여 제거 할 수 있습니다.

    와이즈 비즈  기본값은 0.75이므로 초기 용량은 load_factor 보다 큽니다.  필요합니다. 와이즈 비즈  이 요구 사항을 충족하는 간단한 표현입니다.

    numbers.length * 4/3

  • 이전 c# - 클라이언트 응용 프로그램의 DTO를 서비스 프록시의 DataContract에 매핑
  • 다음 recursion - 재귀 적으로 정의 된 JavaScript isEven () 함수