#1 Two Sum

문제링크 - https://leetcode.com/problems/two-sum/

문제 조건

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• 유효한 답은 하나만 있다.

문제 해결

문제 해결 로직

브루트 포스를 사용하여 목표값과 같으면 반환하여 해당 문제를 쉽게 해결할 수 있다.

데이터 입력

데이터 선언이 필요 없이 해당 배열을 탐색하여 가져온 값으로 문제를 해결할 수 있다.

코드 작성

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

복잡도 계산

• 시간 복잡도

  • 이중 반복문이 사요외어 배열의 길이 n에 따라 O(n^2)의 시간 복잡도를 가진다.

• 공간 복잡도

  • 추가적으로 변수를 선언하지 않고 반환할 때만 공간을 사용하기 때문에 공간 복잡도는 O(1)이다.

회고

• 다음과 같은 점수를 기록했다.
  

• 이중 반복문은 해당 코드를 쉽게 구현할 수 있지만 시간 복잡도에서 상당히 비효율적이다.

• 시간 복잡도를 개선하기 위한 방법은 다음과 같다.

  • 해시맵을 사용하여 배열을 탐색하며 값을 집어넣는다.
  • 만약 현재 위치의 값과 더했을 때 target과 같으면 해당 값으로 배열을 생성하여 반환한다.

class Solution {
    public  int[]  twoSum(int[] nums, int target) {
        Map<Integer,Integer> hashMap =  new HashMap<>();
        for(int i = 0 ; i<nums.length;i++){
            int result = target-nums[i];
            if(hashMap.containsKey(result)){
                return new int[]{hashMap.get(result),i};

            }
            hashMap.put(nums[i],i);
        }
        return new int[] {};
    }
}