1. Two Sum.md

1. Two Sum

1. Description

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]
Output: 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^5
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• Only one valid answer exists.

2. Solutions

Solution 1: Language: C Brute Force

For every number in the array, try to find the corresponding number which equals to target - number.

• Tuesday, 13 October, 2020
• Time Complexity: $O(n^{2})$
• Space Complexity: $O(1)$
• Runtime: 128 ms, faster than 71.18% of C online submissions for Two Sum.
• Memory Usage: 6.7 MB, less than 31.87% of C online submissions for Two Sum.

// Note: The returned array must be malloced, assume caller calls free().
int *twoSum(int *nums, int numsSize, int target, int *returnSize) {
    *returnSize = 2;
    // Create an empty array by the size given. In this problem, the length of
    // returned array should be always "2".
    int *output = (int *)malloc((*returnSize) * sizeof(int));
    // Locate the first number to find if there is another one.
    for (int i = 0; i < numsSize; i++) {
        int diff = target - nums[i];
        for (int j = i + 1; j < numsSize; j++) {
            if (nums[j] == diff) {
                // `i <= j;` should be always True.
                output[0] = i;
                output[1] = j;
            }
        }
    }
    // Return a pointer to the output array.
    return output;
}

3. Notes

• Because we could always find exactly one solution, so there is no need to check boundary cases.
• However, for more typical cases, the function might return an empty array.
• break; might be helpful for boundary cases.
• Question: How to check if the returned array is empty?