当前位置：首页 > article >正文

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

article 2024/10/22 13:50:50

坚持按题型打卡&刷&梳理力扣算法题系列，语言为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)-1
    for {
        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
}