[NeetCode-LeetCode] Two Integer Sum II JAVA

반응형

728x90

[NeetCode-LeetCode] Two Integer Sum II - Medium

---

접근

• 투 포인터

---

풀이

정렬된 배열이 주어질 때 배열 내 두 원소를 더 해 target 값을 만드는 경우 두 원소가 위치한 순서를 반환하는 문제이다. 배열이 [2, 7, 11, 15]이고 target = 9인 경우에 9를 만들기 위해 0번지의 2와 1번지의 7을 더하면 되는데 인덱스 값을 반환하는 것이 아니라 인덱스에 1을 더한 값을 반환해야 한다. 테스트는 정확하게 1개의 해가 나오게 주어지기 때문에 항상 성공이 가능한 경우라고 보면 된다. 추가로 상수 공간만 사용해서 해결하라는 조건도 있다. 

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

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

            if (sum == target) {
                return new int[]{start + 1, end + 1};
            } else if (sum > target) {
                end--;
            } else {
                start++;
            }
        }
        
        return null;
    }

정렬된 배열이다 보니 앞 뒤 두 개의 포인터를 사용해 구해주었다. 두 포인터의 값을 더 해 target 값이라면 결과로 반환하고 더한 값이 target 보다 크다면 오른쪽 포인터를 감소시켜 작은 값을 더하게 하고 target 보다 작다면 왼쪽 포인터를 증가시켜 값을 증가시켜 줬다. 추가 공간으로 start, end, sum과 같은 단일 정수 변수만 사용했기 때문에 상수 공간 사용을 만족했다. 

---

전체 코드

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

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

            if (sum == target) {
                return new int[]{start + 1, end + 1};
            } else if (sum > target) {
                end--;
            } else {
                start++;
            }
        }
        
        return null;
    }
}