leetcode Twosum 문제 풀이

리트코드 1번 문제인 twosum 문제를 풀어보도록 하겠습니다.

다양한 방법이 있겠지만 효율성이 높은 로직을 활용해보도록 하겠습니다.

 

문제. 

[요약]. nums 배열이 , target 값이 주어질때 nums 배열중 2개 숫자의 합이 target값이 되는 두개 숫자의 인덱스 번호를 

배열로 생성해서 출력해라.

 

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.

 

가장 처음 생각나는 방법은 이중 for문으로 전체 검색을 하면 되겠지만 성능상 효율이 떨어진다. (O(n2))

map에 데이터를 저장해서 체크하는 방식으로 처리 하면 for loop 한번으로 처리 가능하다.( O(n) )

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

1. map 객체 하나 생성

2. 전달받은 nums 배열에 대해 0번 인덱스부터 마지막까지 확인하는 for loop 작성 

3. 두개의 합이 될 target 파라미터에서 i번째 nums[i] 의 데이터 값을 빼준 결과 값은 nums[i] 와 함께 twosum 조합이 결과값이 된다.

즉, [2,7,11,12] 배열에서 target=9 일때,

     for loop 를 시작하면 제일 처음 첫번째 배열값인 2에 접근하게된다.

     이제 2와 다른 값을 합쳐 9를 만들어야하는데 결국, target- nums[0] , 즉 9-2= 7  7을 찾아야한다. 이 7을 찾는 과정을 

int secondNum = target - nums[i]; 로 처리한다.

4. 이제 map에는 Loop를 돌때마다 검색한 데이터값과, 데이터값의 배열 인덱스번호를 저장한다. 

    먼저 map에서 검색한 값과 합이 되어야할 값을 검색해준다. 

    target 9, 첫번째 원소가 2라면  7을 key값으로 map에서 조회해본다. 

4-1. map에 해당하는 데이터가 없을 경우 map.put() 메소드를 활용해서 해당 loop의 데이터를 저장해준다.( key = nums[i], val= i)

4-2. map에 해당하는 데이터가 있을경우 int[] 2개 데이터의 인덱스번호를 갖는 배열을 생성해준다.

         아래 if문 분기처리는 사실 해주지 않아도 통과되긴한다. 하지만, 문제에서는 가장 작은 index 번호부터 출력하는 것으로 보여 아래 처리를 해준다.

                if (map.get(secondNum) > i) {
                  return new int[]{i, map.get(secondNum)};
                } else {
                  return new int[]{map.get(secondNum), i};
                }