[LeetCode] problem 1. Two Sum

Description.
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.

---

 이 문제를 보고 가장 처음 든 생각
1. 반복문을 돌려야 되는데 중복을 피해야겠다

2. 정렬을 해야할까?

였다.

 

 

첫 번째 풀이 [통과]

 : "반복문을 돌려야 하는데 중복을 피해야겠다"라는 생각을 갖고 돌려봤다.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int numsLength = nums.length;
        int[] result = new int[2];
        for(int i = 0; i < numsLength; i++){
            for(int j = i+1; j < numsLength; j++){
                int sum = nums[i] + nums[j];
                if(sum == target){
                    result[0] = i;
                    result[1] = j;
                }
            }
        }
        return result;
    }
}

결과는 일단 통과는 했는데

Runtime : 148ms

Memory : 41.9MB

 

시간 복잡도는 N^2으로 너무 비효율 적인 것 같아 개선해보고 싶었다.

---

두 번째 풀이 [실패]

: 정렬을 하면 이분 탐색 느낌으로 반복 횟수를 줄일 수 있지 않을까?

정렬을 한다면, 원본 배열의 인덱스와 값을 갖고 있어야겠다.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int inputArrLength = nums.length;
        int[] result = new int[2];
        HashMap<Integer, Integer> InputArrIndexAndValue = new HashMap<>(inputArrLength);
        for(int i = 0; i < inputArrLength; i++){
            InputArrIndexAndValue.put(nums[i], i);
        }
        
        Arrays.sort(nums);
        
        int[] sortedInputArr = new int[inputArrLength];
        for(int i = 0; i < inputArrLength; i++){
            sortedInputArr[i] = nums[i];
        }
        
        int start = 0;
        int end = inputArrLength - 1;
        
        while(start < end){
            if((sortedInputArr[start] + sortedInputArr[end]) < target){
                start++;
            } else if ((sortedInputArr[start] + sortedInputArr[end]) > target){
                end--;
            } else {
                result[0] = InputArrIndexAndValue.get(sortedInputArr[start]);
                result[1] = InputArrIndexAndValue.get(sortedInputArr[end]);
            }
        }
        return result;
    }
}

결과는 Time out 

Hash 초기화(N) 해주고, 정렬(최악 N^2)하고, 정렬한 배열 초기화(N) 해주고, while문 (logN) 돌려면...

N + N^2 + N + logN... 딱 봐도 망했다...

 

---

세 번째 풀이 [Coming soon]

: 정렬이고 뭐고 nums 안에 2개의 값의 합이 target 이니까, target에서 nums 값 하나를 빼면 나머지 값이 나온다는 뜻인데!! 오늘은 늦었으니 내일 더 생각해보자

coming soon~