Two Sum II - Input Array Is Sorted - 리트코드

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted

한 가지 알아낸 게 있다. 런타임이 하위권이 나올 때가 가끔 있다.
정말 내 풀이가 시간복잡도상 안좋은 걸수도 있는데, 잘 풀었음에도 아래와 같은 그래프가 나와서일수 있다.

평가

결과 : 성공
풀이시간 : 16분

아이디어

• 한 점을 선택합니다.
• 해당 점과 다른 점을 선택합니다. 1, 2번을 고르나 2,1 번을 고르나 같은 경우이기 때문에 배열에서 자신보다 뒤에 값들만을 선택합니다.
• 선택한 두 값을 더해보고 target과 일치하는지 확인합니다.
• 정렬된 값이기 때문에 이분탐색을 사용해서 시간복잡도를 줄여줍니다.

수도코드

selected;// 점을 선택한다

// selected와 함께 고를 점을 선택한다.
start = selected + 1;
end = 끝인덱스;

while(start < end) {
  mid = (start + end) / 2;

  // 현재 두 점 크기 합이 target보다 더 작을경우 -> 더 큰값을 만들어야함 -> start를 옮김
  if (nums[mid] + nums[selected] < target) {
  	start = mid + 1;
  } else if (두 점 크기 합이 target보다 클 경우 ) {
    end = mid;
  } else {
    // 정답
    return [start인덱스 + 1, end인덱스 + 1];
  }
}

정답 코드

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for(int selected = 0; selected<numbers.length; selected++) {
            int start = selected + 1;
            int end = numbers.length; // 끝선
            while(start < end) {
                int mid = (start + end) / 2; // int범위
                int result = numbers[mid] + numbers[selected];
                if(result > target) {
                    end = mid;
                } else if (result < target) {
                    start = mid + 1;                    
                } else {
                    return new int[] {selected + 1, mid + 1};
                }
            }
        }
        return new int[2];
    }
}