[LeetCode] 1. Two Sum

Problem

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

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

Constraints:

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n^2) time complexity?

---

Logic

• 배열 속 두 요소의 합을 파악하기 위해서는 아래와 같이 배열 속 요소들을 일일이 더해보아야 한다.

  nums = [2,7,9,15], target = 9
  // if (1번째 요소 + 1번째 요소 == target) no need for same element
  if (1번째 요소 + 2번째 요소 == target)
  if (1번째 요소 + 3번째 요소 == target)
  if (1번째 요소 + 4번째 요소 == target)
  // if (2번째 요소 + 1번째 요소 == target) no need for duplication
  // if (2번째 요소 + 2번째 요소 == target) no need for same element
  if (2번째 요소 + 3번째 요소 == target)
  ...
  

  Code

  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)
                    return new int[]{i, j};
        return new int[]{0, 0};
    }
  }
  

  Time Complexity

• 반복문을 세부적으로 보았을 때 다음과 같은 계산 횟수를 구할 수 있다.

  if (1번째 요소 + 2번째 요소 == target)
  if (1번째 요소 + 3번째 요소 == target)
  if (1번째 요소 + 4번째 요소 == target)
                ...
  첫 번째 요소의 계산 수 => n - 1
  ---
  if (2번째 요소 + 3번째 요소 == target)
  if (2번째 요소 + 4번째 요소 == target)
                ...
  두 번째 요소의 계산 수 => n - 2
  ---
  if (3번째 요소 + 4번째 요소 == target)
                ...
  세 번째 요소의 계산 수 => n - 3
  ---
  (n - 1) + (n - 2) + (n - 3) + ... + 1 = n * (n - 1) / 2
  

• 따라서 본 솔루션는 O(n^)의 시간복잡도를 가진다.