题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(N^2) 的算法吗？

思路

最简单的方式是采用暴力破解的方式，即遍历两遍数组，判断两两相加的元素是否等于目标值，若相等则记录数组下标。这样的算法时间复杂度为O(N^2)。

我的解题思路是对数组进行排序，这样就可以利用O(logN)的二分查找算法配合对数组的遍历得到O(N*logN)的时间复杂度，满足题目中“进阶”的要求，代码如下：

import "sort"

func twoSum(nums []int, target int) []int {
    original := make([]int, len(nums))
    copy(original, nums)
    sort.Ints(nums)
    results := []int{}

    for i := 0; i < len(nums); i++ {
        results = append(results, i)
        value := target - nums[i]
        j := bSearch(value, i+1, nums)
        if j != -1 {
            results = append(results, j)
            break
        }
        
        results = []int{}
    }
    index := []int{}
    for idx, num := range original {
        if nums[results[0]] == num {
            index = append(index, idx)
            continue
        }
        if nums[results[1]] == num {
            index = append(index, idx)
            continue
        }
    }
    return index
}

func bSearch(value, start int, slice []int) int {
    left := start
    right := len(slice) - 1
    middle := -1
    for left <= right {
        middle = (left + right) / 2
        if slice[middle] < value {
            left = middle + 1
        } else if slice[middle] > value {
            right = middle - 1
        } else {
            return middle
        }
    }
    return -1
}

运行了四遍才最终通过题目测试，原因是我没有看清楚题目给的边界条件，没有考虑负数和0的情况。

查看官方题解，发现有一种O(N)的算法，是利用了散列表来实现的，即用空间换时间的算法：

func twoSum(nums []int, target int) []int {
    hashTable := map[int]int{}
    for i, x := range nums {
        if p, ok := hashTable[target-x]; ok {
            return []int{p, i}
        }
        hashTable[x] = i
    }
    return nil
}