Leetcode-02-Two Sum

title: Leetcode-02-Two Sum
date: 2022-02-12 22:23:14
toc: true
index_img: https://b3logfile.com/file/2022/02/image-51e4a586.png
category:

leetcode
tags:
leetcode

Brute Force#

Enumerate each number x in the array and check if there exists target-x in the array.

func twoSum(nums []int, target int) []int {
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			if nums[j] == target-nums[i] {
				return []int{i, j}
			}
		}
	}
	return nil
}

In the worst case, any two numbers in the array need to be matched once.

Hash Table#

The brute force enumeration method has a high time complexity for finding target - x, so we can create a hash table to solve this problem.

func twoSum(nums []int, target int) []int {
	result := make(map[int]int, 0)
	for index, value := range nums {
		if val, ok := result[target-value]; ok {
			return []int{index, val}
		}
		result[value] = index
	}
	return nil
}

References#

Original question link: 1. Two Sum - LeetCode