剑指 57. 和为s的两个数字

剑指 Offer 57. 和为s的两个数字

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s
输入：nums = [2,7,11,15], target = 9 输出：[2,7] 或者 [7,2]

//对撞指针，时间On，空间O1
func twoSum(nums []int, target int) []int {
    left := 0
    right := len(nums) -1
    for left < right {
        sum := nums[left] + nums[right] 
        if sum == target {
            return []int{nums[left], nums[right]}
        } else if target < sum {
            right--
        } else if target > sum {
            left++
        }
    }
    return nil
}

解题思路
给的数字数组是升序排列的，故用双指针法求解：
定义双指针分别指向数组头尾，即最小、最大的数

• 判断左右指针对应的数之和，与目标数的关系：计算和 sum 是否= nums[i] + nums[j]；
• 若sum > 大于目标数，就需要小一点，则右指针right左移，right—
• 若sum < 小于目标数，就需要大一点，则左指针left右移，left++
• 若sum 等于目标数，这两个数就是要求的数，立即返回数组nums[i],nums[j]

//哈希表法 时空都是On，类似两数之和
func twoSum(nums []int, target int) []int {
    m := make(map[int]struct{})

    for _,v :=range nums{
        if _,ok:=m[target-v];ok{
            return []int{target-v,v}
        }else {
            m[v]= struct{}{}
        }
    }
    return nil
}