[LeetCode] 1. Two Sum - Easy

처음 이 문제를 보고 비웃었다.

시간 복잡도 O(n^2)방법은 쉽게 생각해냈지만, 더 나은 방법은 찾아낼 수 없었다.

다른 사람의 솔루션을 보고 O(nlogn)까지 가능하다는 것을 알게 되었다.

+ HashMap을 사용할 경우 O(n)까지 가능... 심지어 쉬움.

쉬운 문제에서도 배울 점이 있구나...

 

문제 설명

문제는 간단하다. 

input : nums = [2,7,11,15], target = 9
output : [0,1]

input으로는 정수 배열과, target 숫자가 들어온다.

이 때, 정수 배열에서 서로 다른(index가 다른) 두 원소의 합이 target이 되는 index 배열을 리턴하는 것이다.

 

제약사항은 아래와 같다.

2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9

 

쉬운 풀이 방법 - 이중 for

- 누구나 쉽게 생각할 수 있는, for문 두개를 사용하여 푸는 방법.

- 시간 복잡도는 O(n^2)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int size = nums.length;
        for(int i=0; i<size-1; i++){
            for(int j=i+1; j<size; j++){
                if(nums[i]+nums[j]==target) {
                    int[] ans = {i,j};
                    return ans; // 반드시 하나의 solution은 존재한다고 가정하였기 때문에 이와 같이 작성함.
                }
            }
        }
        return null;
    }
}

HashMap 방법 : 제일 빠름 ㅇ.ㅇ

- target - num[i] 를 key로 하는 hashmap을 활용..

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int size = nums.length;

        Map<Integer, Integer> map = new HashMap<>();

        for(int i=0; i<size; i++){
            if(map.get(nums[i])!=null){
                return new int[]{map.get(nums[i]), i};
            }
            map.put(target-nums[i], i);
        }
        return null;
    }
}

 

Binary Search 방법.

- 1. sorting

- 2. binary search 진행. > 솔루션 도출.

 

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int size = nums.length;

        ArrayList<Integer> indices = new ArrayList<>();
        for(int i=0; i<nums.length; i++){
            indices.add(i);
        }
        // 배열의 값을 기준으로 index를 정렬함(good)
        indices.sort((i1,i2)-> nums[i1]-nums[i2]);

		//max에 해당하는 값 커트 해줌.
        int eend=size;

        for(int i=0; i<size; i++){
            // search하고자 하는 수. 
            int val = nums[indices.get(i)];
            int start=i+1;
            int end= eend;
            int mid;
            while(start<end){
                mid=(start+end)/2;
                if(nums[indices.get(mid)]+val >target){
                    eend=mid; // 
                    end=mid;
                }else if(nums[indices.get(mid)]+val <target){
                    start=mid+1;
                }else{
                    int[] rVal = {indices.get(i), indices.get(mid)};
                    return rVal;
                }
            }
        }
        return null;
    }
}