[LeetCode/Java] 1. Two Sum (easy)

Problem

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

LeetCode - The World's Leading Online Programming Learning Platform

 

Solution

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int result1 = 0;
        int result2 = 0;

        for(int i = 0; i < nums.length-1; i++){
            target -= nums[i];
            for(int j = i+1; j < nums.length; j++){
                if(target - nums[j] == 0){
                    result1 = i;
                    result2 = j;
                    break;
                }
            }
            target += nums[i];
        }
        return new int[]{result1, result2};
    }
}

 

(좀 더 간결한 풀이)

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i = 0; i < nums.length -1; i++){
            for(int j = i+1; j < nums.length; j++){
                if(nums[i] + nums[j] == target)
                    return new int[]{i, j};
            }
        }
        return new int[]{};
    }
}

(출처 : https://the-dev.tistory.com/48)

 

Result

시간 복잡도

이중 for 문 사용으로 O(n^2)

 

Comment

이중 for 문을 이용하여 쉽게 해결하였다.

문제에 보면 맨 마지막에 follow-up 을 보면 O(n^2) 의 시간 복잡도보다 낮게 해결 가능하냐는데 아직 나는 못한다...

 

(IntelliJ 로 풀어볼 때)

import java.util.Scanner;

public class LC01 {
    public static void main(String[] args) {
        int count = 0;      // 입력 받을 숫자 수
        int[] num;          // 입력 받은 정수가 저장되는 배열
        int target = 0;
        int result1 = 0;
        int result2 = 0;

        Scanner sc = new Scanner(System.in);
        count = sc.nextInt();
        num = new int[count];

        for (int i = 0; i < count; i++){
            num[i] = sc.nextInt();
        }

        target = sc.nextInt();

        for(int i = 0; i < count-1; i++){
            target -= num[i];
            for(int j = i+1; j < count; j++){
                if(target - num[j] == 0){
                    result1 = i;
                    result2 = j;
                    break;
                }
            }
            target += num[i];
        }
        System.out.println("["+result1+","+result2+"]");
    }
}