[LeetCode] 1_twosum 시간복잡도 관련 문제

[Kang-bh]

Code

/*
    1 아이디어 : nums.length 가 최대 10^4 이기에 완전탐색 수행
    2 시간복잡도 : O(n*m)
    3 자료구조 및 풀이 : 배열, Brute Force
 */


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

        return results;
    }
}

실제 RunTime

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

이를 더 줄일 수 있는 방법??

• HashMap을 이용한 탐색속도 향상