Two Sum II - 입력 배열이 정렬됨

3881 단어 javaleetcodealgorithms
리트코드 문제: Two Sum II - Input Array Is Sorted

목적:

정렬된 배열과 대상 합계가 주어지면 대상 합계가 되는 두 인덱스를 찾습니다.


패턴: 두 포인터 기술


접근하다:
  • 배열의 시작 부분에 하나의 포인터가 있고 배열의 끝에 하나의 포인터가 있습니다.
  • 두 인덱스에 대해 크기 2로 출력 int [] 배열을 초기화합니다.
  • 시작 인덱스가 끝 인덱스보다 커서는 안 되기 때문에 start < end인 조건과 함께 while 루프를 사용합니다. 이것은 우리가 이미 왼쪽과 오른쪽에서 모든 요소를 ​​확인했음을 의미합니다.
  • while 루프 내에서 현재 합계가 대상과 같은지 확인합니다. 그렇다면 인덱스를 반환합니다.
  • 현재 합계가 목표보다 작으면 시작 인덱스를 증가시킵니다.
  • 현재 합계가 목표보다 크면 끝 인덱스를 줄입니다.



    • 빅오 표기법:

    시간 복잡도: O(n)
    각 요소에 대해 while 루프를 n번 반복합니다.

    공간 복잡도: O(1)
    우리는 저장을 위해 추가 데이터 구조를 사용하지 않습니다.

    암호:

    class Solution {
    public int[] twoSum(int[] numbers, int target) {
        // use two pointer techique because the input is sorted.
        int start = 0; 
        int end = numbers.length - 1;
        int [] result = new int [2];

        while (start < end){
            int sum = numbers[start] + numbers[end];

            if (sum == target){
                result[0] = start + 1;
                result[1] = end + 1;
                break;
            }

            if (sum < target){
                start++;
            } else {
                end--;
            }
        }
        return result;
    }
}
    VisualStudio2017LocalDB 연결 방법
    인터뷰 문제 - FizzBuzz

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage