/**
 * 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(n2) time complexity?
 * @see <a href="https://leetcode.com/problems/two-sum/">LeetCode</a>
 */
fun twoSum(nums: IntArray, target: Int): IntArray {
    val map = HashMap<Int, Int>()
    /*
     * Based on the assumption that each input would have exactly one solution, we can safely override the values of
     * repeated keys, knowing they won't be part of the solution
     */
    for (index in nums.indices) {
        map[nums[index]] = index
    }

    for (index in nums.indices) {
        val targetComplementIndex = map.get(target - nums[index])
        /*
         * Since we're not allowed to use the same element twice, we need to ensure that the index of the current
         * element is not the same as the index of the element we're looking for
         */
        if (targetComplementIndex != null && targetComplementIndex != index) {
            return intArrayOf(index, targetComplementIndex)
        }
    }
    return intArrayOf()
}

/**
 * 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(n2) time complexity?
 * @see <a href="https://leetcode.com/problems/two-sum/">LeetCode</a>
 */
fun twoSum(nums: IntArray, target: Int): IntArray {
    val map = HashMap<Int, Int>()
    /*
     * Based on the assumption that each input would have exactly one solution, we can safely override the values of
     * repeated keys, knowing they won't be part of the solution
     */
    for (index in nums.indices) {
        map[nums[index]] = index
    }

    for (index in nums.indices) {
        val targetComplementIndex = map.get(target - nums[index])
        /*
         * Since we're not allowed to use the same element twice, we need to ensure that the index of the current
         * element is not the same as the index of the element we're looking for
         */
        if (targetComplementIndex != null && targetComplementIndex != index) {
            return intArrayOf(index, targetComplementIndex)
        }
    }
    return intArrayOf()
}
