[leetCode] Two Sum (JAVA)

 

주어진 nums 배열에서 두 인덱스 값의 합이 target인 인덱스 2개를 찾으면 된다.

풀이 방법은 2가지.

• 2중for문을 사용하면 간단하지만 시간복잡도가 높다는 단점이 있다.
• HashMap을 사용하여 9(target)=2+7  → 9(target)-2=7 원리로 찾는 방법

package leetcode;

import java.util.Arrays;
import java.util.HashMap;

public class TwoSum {
	public int[] twoSum(int[] nums, int target) {
		/*
		for (int i = 0; i < nums.length; i++) {
			for (int j = i + 1; j < nums.length; j++) {
				if (nums[i] + nums[j] == target) {
					return new int[] { i, j };
				}
			}
		}
		*/
		
		HashMap<Integer, Integer> map = new HashMap<>();
		
		for(int i=0; i<nums.length; i++) {
			map.put(nums[i], i);
		}
		
		for(int i=0; i<nums.length; i++) {
			Integer pre = map.get(target - nums[i]);
			if(pre != null && pre != i) {
				return new int[] {i, pre};
			}
		}
		
		return new int[] {};
	}

	public static void main(String[] args) {
		int[] nums = { 1, 4, 7, 8 };
		int target = 11;

		TwoSum t = new TwoSum();
		System.out.println(Arrays.toString(t.twoSum(nums, target)));
	}
}