带你读《图解算法小抄》十九、双指针(2)

简介: 带你读《图解算法小抄》十九、双指针(2)

带你读《图解算法小抄》十九、双指针(1)https://developer.aliyun.com/article/1348034?groupCode=tech_library


1.两数之和

1问题描述:

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

 

示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

2双指针

解题步骤:

  • 首先,我们需要定义一个哈希表(在 JavaScript 中可以使用对象表示),用于保存遍历过程中每个元素的值和对应的索引。
  • 遍历给定的数组 nums,对于每个元素,首先计算 target 与当前元素的差值(称之为 complement)。
  • 检查哈希表中是否存在 complement,如果存在,那么我们已经找到了答案,返回 complement 在哈希表中的索引和当前元素的索引。
  • 如果哈希表中不存在 complement,那么将当前元素的值和索引添加到哈希表中,继续遍历下一个元素。
  • 如果遍历完整个数组都没有找到答案,那么返回 null。

解题框架:

function twoSum(nums, target) {
    // 1. 定义哈希表
    let map = {};    // 2. 遍历数组
    for (let i = 0; i < nums.length; i++) {
        // 3. 计算 complement
        let complement = target - nums[i];        // 4. 检查哈希表
        if (map[complement] !== undefined) {
            // 5. 如果找到答案,返回答案
            return [map[complement], i];
        } else {
            // 6. 如果没有找到答案,将当前元素添加到哈希表
            map[nums[i]] = i;
        }
    }    // 7. 如果遍历结束还没有找到答案,返回 null
return null;
}

 

 

3基于哈希表

解题步骤:

  • 首先,我们需要定义一个哈希表(在 JavaScript 中可以使用对象表示),用于保存遍历过程中每个元素的值和对应的索引。
  • 遍历给定的数组 nums,对于每个元素,首先计算 target 与当前元素的差值(称之为 complement)。
  • 检查哈希表中是否存在 complement,如果存在,那么我们已经找到了答案,返回 complement 在哈希表中的索引和当前元素的索引。
  • 如果哈希表中不存在 complement,那么将当前元素的值和索引添加到哈希表中,继续遍历下一个元素。
  • 如果遍历完整个数组都没有找到答案,那么返回 null。

解题框架:

function twoSum(nums, target) {
    // 1. 定义哈希表
    let map = {};    // 2. 遍历数组
    for (let i = 0; i < nums.length; i++) {
        // 3. 计算 complement
        let complement = target - nums[i];        // 4. 检查哈希表
        if (map[complement] !== undefined) {
            // 5. 如果找到答案,返回答案
            return [map[complement], i];
        } else {
            // 6. 如果没有找到答案,将当前元素添加到哈希表
            map[nums[i]] = i;
        }
    }    // 7. 如果遍历结束还没有找到答案,返回 null
return null;
}

带你读《图解算法小抄》十九、双指针(3)https://developer.aliyun.com/article/1348032?groupCode=tech_library

相关文章
|
6月前
|
算法
双指针算法
双指针算法
36 2
|
3月前
|
算法 索引 容器
双指针算法详解
本文介绍了双指针算法及其应用。双指针算法是在数组或字符串中常用的高效技术,通过维护两个指针遍历数据结构以解决特定问题。根据指针移动方向,可分为同向双指针、相向双指针和快慢指针。同向双指针如移动零和复写零问题;快慢指针如快乐数问题;相向双指针如盛水最多的容器、有效三角形数量及多数之和等问题。通过合理运用双指针技巧,可简化代码并提高效率。
73 4
双指针算法详解
|
6月前
|
机器学习/深度学习 搜索推荐 算法
【再识C进阶2(下)】详细介绍指针的进阶——利用冒泡排序算法模拟实现qsort函数,以及一下习题和指针笔试题
【再识C进阶2(下)】详细介绍指针的进阶——利用冒泡排序算法模拟实现qsort函数,以及一下习题和指针笔试题
|
2月前
|
算法 C++
【算法】双指针+二分(C/C++
【算法】双指针+二分(C/C++
|
4月前
|
算法 容器
【算法】双指针
【算法】双指针
|
4月前
|
算法 C++ 容器
【C++算法】双指针
【C++算法】双指针
|
7月前
|
算法
【优选算法】——双指针——15. 三数之和
【优选算法】——双指针——15. 三数之和
【优选算法】——双指针——15. 三数之和
|
7月前
|
存储 人工智能 算法
c++算法学习笔记 (9) 双指针
c++算法学习笔记 (9) 双指针
|
7月前
|
算法
[优选算法]——双指针——Leetcode——1089. 复写零
[优选算法]——双指针——Leetcode——1089. 复写零