【力扣打卡系列】滑动窗口与双指针(两数之和)

坚持按题型打卡&刷&梳理力扣算法题系列，语言为go，Day1

两数之和

• 题目描述
  
• 解题思路
  • 采用哈希表
    • 将nums[i] + nums[j] = target 转化成 nums[i] = target - nums[j]去思考
    • 新建一个map来存储，键为值（左边的），值为索引
    • 遍历数组nums的时候，先将当前键进行比对检验（看target - x键是否存在，存在就是找到了）
      • 如果没找到的话就先把当前的nums[j]作为当前map键（x，也就是nums[j]对应的值）值（j，也就是当前nums的索引）存进去
• 代码参考

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

两数之和——输入有序数组

• 题目描述
  
• 解题思路
  • 使用双指针
    • 因为有序，如果和已经比target小了，那么前面的值就可以不要了（操作表现为左指针后移）
    • 同理，如果当前和已经比target大了，那么后面的值就可以不要了（操作表现为左指针前移）
• 代码参考

func twoSum(numbers []int, target int) []int {left,right :=0, len(numbers)-1for {if numbers[left] + numbers[right] == target{return []int{left+1,right+1}}if numbers[left] + numbers[right] > target{right--}if numbers[left] + numbers[right] < target{left++}}return nil
}

• tips
  • for{}直接写=while true的效果
  • 定义了未使用的变量会报错
  • go中获取数组长度用len（nums）-1，注意根据题目要求决定要不要-1