1. 两数之和

题意

解题思路:

• 暴力破解： Time: O(n^2), Space: O(1)
• 哈希表： Time: O(n), Space: O(n)

PHP 代码实现

class Solution {
    function twoSum($nums, $target) {
        $map = [];
        for ($i = 0; $i < count($nums); $i++) {
            $needNum = $target - $nums[$i];
            if (isset($map[$needNum])) return [$map[$needNum], $i];
            $map[$nums[$i]] = $i;
        }
        return [0, 0];
    }
    function twoSumByBruteForce($nums, $target) {
        for ($i = 0; $i < count($nums); $i++) {
            for ($j = $i + 1; $j < count($nums); $j++) {
                if ($nums[$i] + $nums[$j] == $target) return [$i, $j];
            }
        }
    }
}

GO 代码实现

func twoSum(nums []int, target int) []int {
    twoSum1(nums, target)
    tmp, res := make(map[int]int,0),[]int{}
    for _, v := range nums{
        if _, ok := tmp[target - v]; ok {
           res = append(res, v, tmp[target - v])
           return res
        }
        tmp[v] = v
    }
   return res;
}
func twoSumByBruteForce(nums []int, target int) []int {
   for i := 0; i < len(nums); i++ {
        for j := i+1; j < len(nums); j++ {
            if nums[I] + nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return nil
}