題目描述

給定一個整數(shù)數(shù)組 nums 和一個整數(shù)目標值 target，請你在該數(shù)組中找出 和為目標值 target 的那 兩個 整數(shù)，并返回它們的數(shù)組下標。

你可以假設每種輸入只會對應一個答案。但是，數(shù)組中同一個元素在答案里不能重復出現(xiàn)。

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

示例 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) 的算法嗎？

思路

最簡單的方式是采用暴力破解的方式，即遍歷兩遍數(shù)組，判斷兩兩相加的元素是否等于目標值，若相等則記錄數(shù)組下標。這樣的算法時間復雜度為O(N^2)。

我的解題思路是對數(shù)組進行排序，這樣就可以利用O(logN)的二分查找算法配合對數(shù)組的遍歷得到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
}

運行了四遍才最終通過題目測試，原因是我沒有看清楚題目給的邊界條件，沒有考慮負數(shù)和0的情況。

查看官方題解，發(fā)現(xiàn)有一種O(N)的算法，是利用了散列表來實現(xià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
}