[LeetCode- Ch3. 배열] 1. 두개 합 (+ Map)

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

Two Sum - LeetCode

 

1. 조건을 만족하는 단 하나의 값만 존재

-> 이중 For문 

class Solution {
    static int[] arr;
    public int[] twoSum(int[] nums, int target) {
        //두개 합
        //정수 배열과 정수
        arr=nums;
        int n=nums.length;
        int[] answer=new int[2];
        //정수 배열에서 2개를 더해 target이 나온다. -> 단 하나만 존재
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(nums[i]+nums[j]==target) {
                    answer[0]=i;
                    answer[1]=j;
                }
            }
        }
        
        return answer;
    }
    
}

 

---

시간복잡도 O(n)으로 만들기 위해

-> Map(숫자, 인덱스) 이용

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n=nums.length;
        int[] answer= new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<n;i++){
            map.put(nums[i], i);
        }
        for(int i=0;i<n;i++){
            int tmp=target-nums[i];
            if(map.containsKey(tmp)&&map.get(tmp)!=i) {
                return answer=new int[]{i,map.get(tmp)};
            }
        }
        return answer;
    }
}

 

+) 세련된 풀이

Map(원하는 값 - 배열값, 인덱스) 생성

-> (배열값이 map에 존재하면 == 두 개의 합이 target이 되는 값 존재)한다면 각각의 인덱스를 저장

class Solution {
    public int[] twoSum(int[] nums, int target) {
		//1. ds
		int[] result = new int[2];
		Map<Integer, Integer> map = new HashMap<>();

		//2. for
		for(int i=0; i<nums.length; i++) {
			if(map.containsKey(nums[i])) {
				int val = map.get(nums[i]); //14
				result[0] =val;
				result[1] = i;
			}else {
				map.put(target-nums[i], i);
			}
		}
		return result;
	}
}