[LeetCode] 167. Two Sum II - Input Array Is Sorted

Two Sum II - Input Array Is Sorted - LeetCode

 

int 배열 numbers와 tartget 숫자가 주어지면 numbers안에 요소 2개를 더해 target이 되는 인덱스들을 반환하는 문제입니다.

 

문제접근

문제는 단순하게 접근하였습니다.

배열안에서 두개의 값을 비교해야하기때문에 투포인터를 사용해봐야겠다고 생각했습니다.

 

start와 end를 정해두고 num[start] + num[end]가

target보다 크다면 end-- 

target보다 작다면 start++

target과 같다면 start+1, end+1을 반환하였습니다.

 

   public int[] twoSum(int[] numbers, int target) {
        int start = 0;
        int end = numbers.length-1;

        while (start <= end){
            int cur = numbers[start] + numbers[end];
            System.out.println(cur + " " + start + " " + end);
            if (cur > target) {
                end--;
            } else if (cur < target) {
                start++;
            } else {
                return new int[]{start+1, end+1};
            }
        }

        return new int[]{};
    }

 

 

시간복잡도

최악의 경우 end 또는 start가 끝까지 가야하므로 O(n)의 시간복잡도를 갖고있습니다.

 

다른사람의 풀이

같은 투포인터를 사용했지만, while문의 조건을 더 잘 활용하였습니다.

 

public int[] twoSum(int[] nums, int target) {
	int l = 0, r = nums.length - 1;
	
	while (nums[l] + nums[r] != target) {
		if (nums[l] + nums[r] < target) l++;
		else r--;
	}

	return new int[] {l+1, r+1};
}

 

느낀점

이번에는 배열의 두요소를 컨트롤해야한다는 점을 알고 투포인터를 잘 활용한것 같습니다.

하지만 while문을 잘 활용하기위해 while문의 조건을 좀 더 잘 다뤄야겠다고 생각했습니다.

 

그이유는 조건을 잘 설정하면 코드의 가독성이 더 높아지기 때문입니다.

 

참고  

Two Sum II - Input Array Is Sorted - LeetCode