1. Two Sum

1. Two Sum

英文题目

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

题目大意

给定一个数组和一个数,求解相加等于这个数的数组下标。

解题思路

Solution1

2次循环暴力破解

func TwoSum(nums []int, target int) []int {
    n := len(nums)
    for i, v := range nums {
        for j := i + 1; j < n; j++ {
            if v+nums[j] == target {
                return []int{i, j}
            }
        }
    }

    return nil
}

Complexity Analysis

  • 时间复杂度:O(n2)。2次百里循环所以时间复杂度是O(n2)。
  • 空间复杂度:O(1)

Solution2

利用HASHMAP,全部操作都在一层循环中完成。

func TwoSum(nums []int, target int) []int {
    m := make(map[int]int, len(nums))
    for i, v := range nums {
        sub := target - v
        // MAP中存在满足要求的数直接返回
        if j, ok := m[sub]; ok {
            return []int{j, i}
        // 如果当前元素在MAP中不存在则将其PUSH到MAP
        } else {
            m[v] = i
        }
    }

    return nil
}

Complexity Analysis

  • 时间复杂度:O(n)。利用HASHMAP将时间复杂度降低一个数量级。
  • 空间复杂度:O(1)

结语

如果你同我一样热爱数据结构、算法、LeetCode,可以关注我 GitHub 上的 LeetCode 题解:awesome-golang-leetcode


  Reprint please specify: KYLE LIU 1. Two Sum

  TOC