LeetCode 001 - Two Sum (두 수의 합)

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

사고의 방향
이 문 제 는 실제 적 으로 해시 표 의 사용 을 고찰 합 니 다. 배열 을 옮 겨 다 닐 때 이미 옮 겨 다 니 는 요 소 를 해시 표 에 넣 습 니 다 (key 는 배열 요소 이 고 value 는 배열 색인 입 니 다).이렇게 nums [i] 에 옮 겨 다 닐 때 해시 표 에 target - nums [i] 가 있 는 지 판단 하면 됩 니 다.
  • 시간 복잡 도: O (n)
  • 공간 복잡 도: O (n)
  • 자바 구현
    class Solution {
        public int[] twoSum(int[] nums, int target) {
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            for (int i = 0; i < nums.length; i ++) {
                int t = target-nums[i];
                if (map.containsKey(t)) {
                    return new int[] {map.get(t), i};
                }
                map.put(nums[i], i);
            }
            return null;
        }
    }
    

    파 이 썬 구현
    class Solution(object):
        def twoSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            map = {}
            for i in range(len(nums)):
                t = target - nums[i]
                if map.get(t) is not None:
                    return [map.get(t), i]
                map[nums[i]] = i
    

    스칼라 구현
    object Solution {
        def twoSum(nums: Array[Int], target: Int): Array[Int] = {
            var map = Map[Int, Int]()
            var t = 0
            for (i <- Range(0,nums.length)) {
                t = target - nums(i)
                if (map.contains(t)) {
                    return Array(map(t), i)
                }
                map += nums(i) -> i
            }
            return null
        }
    }
    

    좋은 웹페이지 즐겨찾기