๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์ฝ”ํ…Œ

LeetCode Top Interview 150 - 1. Two Sum

๐Ÿค” ๋ฌธ์ œ ์ดํ•ด

์ฃผ์–ด์ง„ ๋ฐฐ์—ด์—์„œ ๋‘๊ฐœ์˜ ์ •์ˆ˜๋ฅผ ๋”ํ•ด target์œผ๋กœ ์ œ์‹œ๋œ ๊ฐ’์„ ๋งŒ์กฑํ•ด๋ผ

https://leetcode.com/problems/two-sum/?envType=study-plan-v2&envId=top-interview-150

๐Ÿค” EX

data example 1
Input: nums = [2,7,11,15], target = 9
Output: [0,1]

data example 2
Input: nums = [2,7,11,15], target = 9
Output: [0,1]

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

 

๐Ÿค” ์˜์‚ฌ ์ฝ”๋“œ

const map = new map() 
for( nums.length){
	let result = target - nums[i]
    map์— result๊ฐ€ ์žˆ๋Š”์ง€ ํ™•์ธ ์žˆ์œผ๋ฉด return
    ์—†์œผ๋ฉด set()
}

 

 

๐Ÿค” ํ•ด๊ฒฐํ•œ ์ฝ”๋“œ : O(n)

var twoSum = function(nums, target) {
    const map = new Map()
    for(let i =0; i<nums.length;i++){
        const result = target - nums[i]
        if(map.has(result)){
            return [map.get(result),i]
        }
        map.set(nums[i],i)
    }
    return 
};

 

๐Ÿค” ๋‹ค๋ฅธ ํ’€์ด๋ฐฉ๋ฒ• : O(n^2)

์•„๋ž˜์˜ ์ฝ”๋“œ์™ธ์—๋Š” ์ž‘์„ฑํ•œ ์ฝ”๋“œ์™€ ๋น„์Šทํ•œ๊ฒƒ ๊ฐ™๋‹ค. ์•„๋ž˜์˜ ์ฝ”๋“œ๋ฅผ ์ƒ๊ฐ ์•ˆํ•ด๋ณธ๊ฑด ์•„๋‹ˆ์˜€์ง€๋งŒ(๋ณด์ž๋งˆ์ž ์ƒ๊ฐํ–ˆ๋‹คใ…‹ใ…‹) ์ค‘์ฒฉ for๋ฌธ์„ ์‚ฌ์šฉํ•˜๋ฉด ์ข‹์„๊ฒƒ๊ฐ™์ง„ ์•Š์•˜๋‹ค. 

var twoSum = function(nums, target) {
  let ans = []; 
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) { 
      let sum = nums[i] + nums[j]; 
      if (sum === target) { 
        ans.push(i);
        ans.push(j);
        return ans; 
      }
    }
  }
  return ans;
}