[LeetCode] 1. Two Some

문제

 

난이도 Easy

 

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

 

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

 

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

 

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

 

 

---

 

배운점

 

IDE를 안쓰고는 코딩 자체가 불가능할 정도로 IDE에 너무 의존하고 있었다는 생각이 들었다.

 

자바 기본을 공부 안해서 배열 문법을 잘 몰랐다. 배열 초기화와 값 조회 방법에 대해서 배웠다. 그리고 배열의 크기는 .length로 조회할 수 있다는 것도 배웠다.

 

Stream을 IDE 없이 쓰려니 힘들다. Stream 문법도 IDE 없이 잘 쓸 수 있도록 연습을 많이 해봐야겠다. 꼭 그럴 필요가 있는건 아니지만...

 

O(N^2)을 극복해봐야겠다.

-> O(N^2)을 극복하기 위해서는 조건문이나, 1차 for문을 통해서 한번 걸러내야 한다.

 

--> leetCode solution을 보고나니, Map 문법에 대해 익숙하지 못하고, 공간 복잡도도 있다는 것을 알게 되었다.

-> O(N^2)이 시간 복잡도이고, 그것을 극복하고자 한다면 공간복잡도를 늘리는 방법을 생각해봐야 한다.

---

 

풀이

 

1차 - 나의 해답

단순 이중 포문 적용

 

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 null;
    }
}

 

 

2차 - leetCode solution

Map을 활용한다. 시간 복잡도를 줄이는 대신, 공간복잡도를 증가시켜서 문제를 해결한다!

 

 

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<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);
        }
        // In case there is no solution, we'll just return null
        return null;
    }
}

 

 

Complexity Analysis

• Time complexity: O(n)O(n). We traverse the list containing nn elements only once. Each lookup in the table costs only O(1)O(1) time.
• Space complexity: O(n)O(n). The extra space required depends on the number of items stored in the hash table, which stores at most nn elements.

---

 

출처

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