[LeetCode] Two Sum 풀이

문제 링크

• https://leetcode.com/problems/two-sum

완전탐색

• 시간복잡도 O(N^2)
• 공간복잡도 O(1)

class Solution {
    public 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 (target == nums[i] + nums[j]) {
                    return new int[]{i, j};
                }
            }
        }

        return new int[]{};
    }
}

 

HashTable

• 시간 복잡도 O(N)
• 공간 복잡도 O(N)

import java.util.*;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            int key = target - nums[i];
            if (map.get(key) != null) {
                int value = map.get(key);

                if (value < i) {
                    return new int[]{value, i};
                } else {
                    return new int[]{i, value};
                }
                
            } else {
                map.put(nums[i], i);
            }
        }

        return new int[]{};
    }
}