1. Two Sum (두 합)

정수 배열 nums 과 정수가 주어지면 두 숫자의 합이 target이 되도록하는 인덱스를 반환합니다.
각 입력에 정확히 하나의 솔루션이 있다고 가정할 수 있으며 동일한 요소를 두 번 사용할 수 없습니다 .
어떤 순서로든 답변을 반환할 수 있습니다.

 

예시 1:

입력: nums = [2,7,11,15], target = 9
출력: [0,1]
설명: nums[0] + nums[1] == 9이므로 [0, 1]을 반환합니다.

 

예시 2:

입력: nums = [3,2,4], target = 6
출력: [1,2]

 

예시 3:

입력: nums = [3,3], target = 6
출력: [0,1]

 

조건:

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• 하나의 유효한 답변만 존재합니다.

제약조건:  시간 복잡도O(n^2) 보다 낮은 알고리즘을 생각해낼 수 있습니까?

 

정답:

public class Solution {
    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)
                {
                    int[] result = {i, j};

                    return result;
                }
            }
        }

        return null;
    }
}

해설: 

첫번째부터 순차적으로 더한 값을 target과 비교해보며 풀었습니다.