[LeetCode] TwoSum

문제 설명:

정수로 이루어진 배열 nums와 하나의 정수 target이 주어졌을 때,
배열 안의 두 숫자를 더해서 target이 되는 두 숫자의 인덱스를 찾아서 반환하세요.

• 각 입력에는 딱 하나의 정답만 존재한다고 가정할 수 있습니다.
• 같은 요소를 두 번 사용할 수는 없습니다.
• 정답은 어떤 순서로든 반환해도 됩니다.

 

시간복잡도: O(n²) 

(가장 비효율적이다)

    public static int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];

        for (int i = 0; i < nums.length; i++) {
            int num1 = nums[i];

            for (int j = 0; j < nums.length; j++) {
                int num2 = nums[j];

                if (i !=j && num1 + num2 == target){
                    result[0] = num1;
                    result[1] = num2;
                }
            }
        }

        return result;
    }

 

 

주어진 nums의 정렬이 안된경우 HashMap 사용 시간복잡도: O(n)

    public static int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];

            if(map.containsKey(complement)){
                return new int[]{ map.get(complement), i };
            }

            map.put(nums[i], i);
        }

        return new int[0];
    }

 

 

주어진 nums의 오름차 정렬된 경우 Two Pointer 방식 사용 시간복잡도: O(n)

(HashMap을 안써서 Heap 메모리 아낌)

    public static int[] twoSumSorted(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;

        while (left < right) {
            int sum = nums[left] + nums[right];
            if(sum == target) return new int[] {left,right};
            else if (sum > target) right--;
            else left++;
        }

        return new int[0];
    }