LeetCode : 167. Two Sum II - Input Array Is Sorted

문제 링크

문제 먼저 읽기

• 오름차순으로 정렬되고 인덱스 1부터 시작하는 배열이 주어집니다.
• 합하여 특정 목표 숫자를 만드는 두 인덱스를 정수 배열로 반환하세요.
• 반환되는 정수 배열은 [index1, index2] 로 길이가 2이며 index1 < index2 입니다.
• 반드시 하나의 해결책이 있습니다. 동일한 요소를 2번 쓸 일은 없습니다.

어떻게 풀까?

생각

• 2개의 pointer로 합을 비교합니다.
• pointer는 양 끝에 위치하여 한쪽 방향으로만 움직이게 합니다. target number와 같으면 멈추고 반환합니다.

수도코드

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int pointerA = 0;
        int pointerB = numbers.length-1;
        
        while (pointerA < pointerB) {
            if (numbers[pointerA] + numbers[pointerB] == target) {
                break;
            }
            if (numbers[pointerA] + numbers[pointerB] > target) {
                pointerB --;
            }
            if (numbers[pointerA] + numbers[pointerB] < target) {
                pointerA ++;
            }
        }
        return new int[]{pointerA, pointerB};
    }
}

• 마지막 반환 값에 오류가 있는 것을 발견해서 수정해서 제출하였습니다.

결과

<aside> 💡 Success

Runtime: 3 ms, faster than 22.50% of Java online submissions for Two Sum II - Input Array Is Sorted.

Memory Usage: 45.7 MB, less than 24.39% of Java online submissions for Two Sum II - Input Array Is Sorted.

</aside>

다른 풀이 방식과 문제 회고

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int p1 = 0;
        int p2 = nums.length-1;
        int[] ans = new int[2];
        
        while(p1 < p2){
            int sum = nums[p1]+nums[p2];     
            if(sum == target){
                ans[0] = p1+1;
                ans[1] = p2+1;
                break;
            }
            else if(sum > target){
                p2--;
            }
            else{
                p1++;
            }
        }
        return ans;
    }
}

• 반복되는 수식을 변수에 저장하면 효율이 조금 개선됩니다.

<aside> 💡 Success

Runtime: 2 ms, faster than 58.23% of Java online submissions for Two Sum II - Input Array Is Sorted.

Memory Usage: 45.3 MB, less than 75.18% of Java online submissions for Two Sum II - Input Array Is Sorted.

</aside>

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int pointerA = 0;
        int pointerB = numbers.length-1;
        
        while (pointerA < pointerB) {
            int sum = numbers[pointerA] + numbers[pointerB];
            if (sum == target) {
                break;
            } else if (sum > target) {
                pointerB --;
            } else {
                pointerA ++;
            }
        }
        return new int[]{pointerA+1, pointerB+1};
    }
}

• if ~ else를 사용하여 속도를 조금 더 개선할 수 있습니다.

<aside> 💡 Success

Runtime: 1 ms, faster than 99.41% of Java online submissions for Two Sum II - Input Array Is Sorted.

Memory Usage: 45.8 MB, less than 17.65% of Java online submissions for Two Sum II - Input Array Is Sorted.

</aside>