[leetcode] 1. two sum - java 자바 문제 풀이

1. Two Sum

배열과 target을 파라미터로 받아

배열 중 두 개의 숫자가 target과 같을 시 그 숫자들의 인덱스 번호를 출력하는 문제 

 

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

 

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

 

> [방법 1] for문으로 하나 하나 비교하는 방법  

물론 정답이 출력되나, 시간 복잡도가 O(N2)이 되어 매우 비효율적.  

    public static int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length - 1; ++i) {
            for (int j = i + 1; j < nums.length; ++j) {
                if (nums[i] + nums[j] == target)
                    return new int[] {i,j};
            }
        }
        return null;
    }

 

> [방법 2]  Hash table 이용한 방법  

 for문이 한 번만 돌아가므로 시간 복잡도는 O(N)가 될 것이다. 

Hash map 에다가 <배열값, 인덱스 번호> 를 대입한다. 

그리고  a+b=target 과 target-a=b 는 같다는 개념을 이용,

만약 배열= [1,2,4,9] , target=6 이라 예를 든다면 target - 2 = 4 가 되고, 4를 찾아 4에 해당하는 인덱스 넘버를 출력하면 된다.  

public static int[] twoSum(int[] nums, int target) {
    // key: index number , value : values --> hash table
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    // put nums, index number to map
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    
    // coparing to target
    for (int i = 0; i < nums.length; i++) {
        Integer remainder = map.get(target - nums[i]);
        if (remainder != null && remainder != i)
            return new int[]{i, remainder};
    }
    return null;
}

 

> [방법 3]  two pointers  : 실패 

정답이 출력되긴 하는데 제출 시 wrong answer 이라고 뜬다.

생각해보니 제출 시에는 다른 케이스를 대입해서 체크하는데, 대입하는 array의 값들이 반드시 오름차순이 아니었던 것.

그래서 포인터로 비교하기 어려웠던 것 같다. 

그렇다면 sorting을 해서  포인터를 움직여야 하는데 index 번호가 바뀌어 버리니까... key, value로 쌍을 만들어 값을 저장했어야 하나..? 

이런 고민 속에 실패.. 누구 답 아시는 분이 있다면 알려주세요..... 

    public static int[] twoSum(int[] nums, int target) {
        // two pointers
        //Arrays.sort(nums); -- 그렇다면 index 번호는...?
        int lp = 0;
        int rp = nums.length - 1;
        int result[] = new int[2];

        while(lp < rp) {
            int sum = nums[lp] + nums[rp];
            if(sum == target) {
                result[0] = lp;
                result[1] = rp;
                break;
            } else if (sum < target) {
                lp++;
            } else {
                rp--;
            }
        }
        return result;
    }