릿코드 two-sum

2020-01-01

1. 릿코드 leetcode two-sum

2. 문제

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.

2.1. Example 1:

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

2.2. Example 2:

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

2.3. Example 3:

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

2.4. Constraints:

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

2.1. 컴퓨팅적 사고

(1). 하나의 값을 기준으로 모든 배열을 탐색하면서 값을 더해나갑니다.
(2). 더해나가는 값 sum이 target값과 같아진다면 해당 i,j의 값을 리턴합니다.
(3). 시간복잡도 부분에서 O(N^2)이 나오기때문에 매우 비효율적인 연산일 수 있기때문에 다른 풀이를 찾아보니 map을 활용하여 문제풀이도 볼 수 있었습니다.

2.2. 소스코드

public class leetcode_TwoSum_kgh {
        public static void main(String[] args) {
            solution(new int[]{2, 7, 11, 15}, 9);
        }
        static void solution(int[] nums, int target) {
        int[] answer = {0,0};
        for(int i=0; i<nums.length; i++){
            int sum = 0;
            for(int j=i+1; j<nums.length; j++){
                sum = nums[i] + nums[j];
                if(sum == target){
                    answer[0] = i;
                    answer[1] = j;
                }
            }
        }
        System.out.println(answer[0] +""+ answer[1]);
    }
}

3. Map을 활용한 풀이

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);
    }
    throw new IllegalArgumentException("No two sum solution");
}

Algorithmleetcode