[PS] TwoSum

 

Two Sum

문제 설명

문제는 간단 정수 배열과 target 이 들어오고 배열 중 2개의 요소 합이 target 을 만족하면 두 값의 인덱스를 출력하는 것

 

조건은 배열안에 무조건 만족하는 솔루션이 하나는 있고 똑같은 요소를 두번 사용하는 경우는 없다는 것

 

해결

1. 부르트 포스

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

티스토리 코드블럭에 자동으로 인덴트 줄여주는거 만들어주면 안되나

그냥 신나게 다 보는 것 겹치지 않게 돌려고 j는 i로 시작을 살짜쿵 +1 해도상관없을 것 같긴하다.

 

시간복잡도 O(n^2)

 

2. HashMap 사용

    public int[] toSumHash(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            int com = target - nums[i];
            if(map.containsKey(com)) {
                return new int[]{map.get(com), i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("Wrong");
    }

HashMap 에 넣어서 남은 값을 map에 찾아내는 기똥찬 방법 HashMap 에서 값 찾아오는게 상수시간이니 모든 element만 보면된다.

 

시간복잡도 O(n)

 

 

끝!