深入解析力扣167题:两数之和 II(双指针法详解及模拟面试问答)

简介: 深入解析力扣167题:两数之和 II(双指针法详解及模拟面试问答)

关注微信公众号 数据分析螺丝钉 免费领取价值万元的python/java/商业分析/数据结构与算法学习资料

在本篇文章中,我们将详细解读力扣第167题“两数之和 II - 输入有序数组”。通过学习本篇文章,读者将掌握如何使用多种方法来解决这一问题,并了解相关的复杂度分析和模拟面试问答。每种方法都将配以详细的解释和ASCII图解,以便于理解。

问题描述

力扣第167题“两数之和 II - 输入有序数组”描述如下:

给定一个已按照升序排列的整数数组 numbers,请你从数组中找出两个数,使得它们的和等于目标数 target。函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。

示例 1:

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1, 2]
解释: 2 与 7 之和等于目标数 9。因此 index1 = 1, index2 = 2。

示例 2:

输入: numbers = [2, 3, 4], target = 6
输出: [1, 3]

示例 3:

输入: numbers = [-1, 0], target = -1
输出: [1, 2]

解题思路

方法一:双指针法
  1. 初步分析
  • 由于数组是有序的,可以使用双指针法高效地找到两个数,使它们的和等于目标数。
  1. 步骤
  • 初始化两个指针,left 指向数组的起始位置,right 指向数组的末尾。
  • 计算 numbers[left]numbers[right] 的和,如果和等于目标数,则返回两个指针的索引。
  • 如果和小于目标数,移动左指针 left 向右。
  • 如果和大于目标数,移动右指针 right 向左。
代码实现
def twoSum(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            return [left + 1, right + 1]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return []
# 测试案例
print(twoSum([2, 7, 11, 15], 9))  # 输出: [1, 2]
print(twoSum([2, 3, 4], 6))  # 输出: [1, 3]
print(twoSum([-1, 0], -1))  # 输出: [1, 2]
ASCII图解

假设输入为 numbers = [2, 7, 11, 15]target = 9,图解如下:

初始化指针:
left = 0, right = 3
第一次比较:
numbers[left] + numbers[right] = 2 + 15 = 17 > 9
移动右指针:
left = 0, right = 2
第二次比较:
numbers[left] + numbers[right] = 2 + 11 = 13 > 9
移动右指针:
left = 0, right = 1
第三次比较:
numbers[left] + numbers[right] = 2 + 7 = 9 == 9
找到目标:
返回 [1, 2]

复杂度分析

  • 时间复杂度:O(n),其中 n 是数组的长度。只需遍历一次数组。
  • 空间复杂度:O(1),只使用了常数级别的额外空间。

模拟面试问答

问题 1:你能描述一下如何解决这个问题的思路吗?

回答:我们需要在有序数组中找到两个数,使它们的和等于目标数。可以使用双指针法:初始化两个指针,分别指向数组的起始位置和末尾位置。计算两个指针指向的数的和,如果和等于目标数,则返回指针的索引;如果和小于目标数,移动左指针;如果和大于目标数,移动右指针。如此循环,直到找到目标数。

问题 2:为什么选择使用双指针法?

回答:由于数组是有序的,使用双指针法可以高效地找到两个数的组合。双指针法的时间复杂度是 O(n),比暴力搜索的 O(n^2) 更高效。

问题 3:你的算法如何处理重复元素?

回答:由于每个输入只对应唯一的答案,所以算法会找到两个数和等于目标数时直接返回结果,不需要考虑重复元素的问题。算法中的比较和移动指针的操作确保了不会重复使用相同的元素。

问题 4:如何处理数组长度小于2的情况?

回答:如果数组长度小于2,不可能找到两个数和等于目标数。可以在算法开始时检查数组长度,如果小于2,直接返回空列表。

问题 5:你能解释一下双指针法的工作原理吗?

回答:双指针法通过初始化两个指针,分别指向数组的起始位置和末尾位置。计算两个指针指向的数的和,如果和等于目标数,则返回指针的索引;如果和小于目标数,移动左指针;如果和大于目标数,移动右指针。这样通过逐步缩小范围,找到目标数。

问题 6:在代码中如何确保返回的索引是从1开始的?

回答:在代码中,返回结果时将指针的索引加1。例如,return [left + 1, right + 1]。这样确保返回的索引是从1开始的,而不是从0开始的。

问题 7:如果数组中没有符合条件的两个数,算法会如何处理?

回答:如果数组中没有符合条件的两个数,算法会在循环结束后返回空列表 [],表示没有找到符合条件的两个数。

问题 8:你能举例说明在面试中如何回答优化问题吗?

回答:在面试中,如果面试官问到如何优化算法,我会首先分析当前算法的瓶颈,如时间复杂度和空间复杂度,然后提出优化方案。例如,对于“两数之和 II - 输入有序数组”问题,使用双指针法可以将时间复杂度优化到 O(n),比暴力搜索更高效。

问题 9:如何验证代码的正确性?

回答:通过多个测试案例验证代码的正确性,包括正常情况和边界情况。例如,测试数组长度小于2的情况,目标数为数组中不存在的情况,数组中有负数的情况等,确保代码在各种情况下都能正确运行。

问题 10:你能解释一下双指针法的适用场景吗?

回答:双指针法适用于有序数组或链表的情况,可以高效地解决查找问题。例如,查找两个数和等于目标数的问题、查找连续子数组和等于目标数的问题等。通过双指针法,可以在 O(n) 时间复杂度内找到答案,比暴力搜索更高效。

总结

本文详细解读了力扣第167题“两数之和 II - 输入有序数组”,通过双指针法高效地解决了这一问题,并提供了详细的ASCII图解和模拟面试问答。希望读者通过本文的学习,能够在力扣刷题的过程中更加得心应手。

参考资料

  • 《算法导论》—— Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
  • 力扣官方题解

欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
3月前
|
存储 安全 Java
2025 最新史上最全 Java 面试题独家整理带详细答案及解析
本文从Java基础、面向对象、多线程与并发等方面详细解析常见面试题及答案,并结合实际应用帮助理解。内容涵盖基本数据类型、自动装箱拆箱、String类区别,面向对象三大特性(封装、继承、多态),线程创建与安全问题解决方法,以及集合框架如ArrayList与LinkedList的对比和HashMap工作原理。适合准备面试或深入学习Java的开发者参考。附代码获取链接:[点此下载](https://pan.quark.cn/s/14fcf913bae6)。
1283 48
|
3月前
|
缓存 NoSQL Java
Java Redis 面试题集锦 常见高频面试题目及解析
本文总结了Redis在Java中的核心面试题,包括数据类型操作、单线程高性能原理、键过期策略及分布式锁实现等关键内容。通过Jedis代码示例展示了String、List等数据类型的操作方法,讲解了惰性删除和定期删除相结合的过期策略,并提供了Spring Boot配置Redis过期时间的方案。文章还探讨了缓存穿透、雪崩等问题解决方案,以及基于Redis的分布式锁实现,帮助开发者全面掌握Redis在Java应用中的实践要点。
191 6
|
3月前
|
NoSQL Java 微服务
2025 年最新 Java 面试从基础到微服务实战指南全解析
《Java面试实战指南:高并发与微服务架构解析》 本文针对Java开发者提供2025版面试技术要点,涵盖高并发电商系统设计、微服务架构实现及性能优化方案。核心内容包括:1)基于Spring Cloud和云原生技术的系统架构设计;2)JWT认证、Seata分布式事务等核心模块代码实现;3)数据库查询优化与高并发处理方案,响应时间从500ms优化至80ms;4)微服务调用可靠性保障方案。文章通过实战案例展现Java最新技术栈(Java 17/Spring Boot 3.2)的应用.
213 9
|
3月前
|
设计模式 安全 Java
Java 基础知识面试题全解析之技术方案与应用实例详解
本内容结合Java 8+新特性与实际场景,涵盖函数式编程、Stream API、模块化、并发工具等技术。通过Lambda表达式、Stream集合操作、Optional空值处理、CompletableFuture异步编程等完整示例代码,助你掌握现代Java应用开发。附面试题解析与技术方案,提升实战能力。代码示例涵盖计算器、员工信息统计、用户查询、模块化系统设计等,助你轻松应对技术挑战。
100 9
|
3月前
|
缓存 Java 索引
2025 年 Java 面试必备最常见 200 + 面试题及答案解析
这是一份针对Java面试的综合技术方案与应用实例文档,涵盖Java基础(JDK/JRE、字符串、IO流)、容器(ArrayList/LinkedList、HashMap)、多线程(线程创建、同步、线程池)、数据库(MySQL索引、Redis缓存穿透)及Spring框架(IOC容器、热部署)等核心模块。通过详细解析常见面试题,帮助读者深入理解并掌握Java核心技术,为应对面试提供全面指导。此外,还涉及反射、设计模式、JVM调优等进阶内容,助力开发者全面提升技能。代码示例可从提供的链接下载。
822 6
|
3月前
|
算法 安全 Java
2025 校招必看:Java 开发面试核心知识点深度解析及最新笔面试题汇总
本文针对2025校招Java开发面试,系统梳理了Java基础、集合框架、多线程并发、JVM等核心知识点,并附带最新笔面试题。内容涵盖封装、继承、多态、异常处理、集合类使用、线程同步机制、JVM内存模型及垃圾回收算法等。同时深入探讨Spring、数据库(MySQL索引优化、Redis持久化)、分布式系统(CAP理论、分布式事务)等相关知识。通过理论结合实例解析,帮助考生全面掌握面试要点,提升实战能力,为成功拿下Offer奠定坚实基础。
379 3
|
3月前
|
存储 缓存 安全
Java 集合容器常见面试题及详细解析
本文全面解析Java集合框架,涵盖基础概念、常见接口与类的特点及区别、底层数据结构、线程安全等内容。通过实例讲解List(如ArrayList、LinkedList)、Set(如HashSet、TreeSet)、Map(如HashMap、TreeMap)等核心组件,帮助读者深入理解集合容器的使用场景与性能优化。适合准备面试或提升开发技能的开发者阅读。
65 0
|
3月前
|
存储 缓存 安全
Java 集合篇面试题全面总结及答案解析
本文总结了Java集合框架的核心概念、常见集合类的特性与应用场景,以及开发中可能遇到的问题与解决方案。内容涵盖集合框架的基础接口(如Collection、Set、List、Map)、泛型的优点、线程安全集合类(如ConcurrentHashMap、CopyOnWriteArrayList)、常见集合类的区别(如ArrayList与LinkedList、HashMap与HashTable)等。此外,还详细介绍了如何实现LRU缓存、FIFO队列、优先级队列及栈等数据结构,并提供了相关代码示例。通过本文,读者可以全面掌握Java集合相关的面试知识点及其实际应用技巧。
131 1
|
3月前
|
存储 Java 数据库
应届生面试高频 Java 基础问题及详细答案解析
摘要: Java数据类型分为基本类型(如int、float等)和引用类型(如类、数组)。final可修饰类、方法和变量,使其不可继承、重写或修改。static用于类级别的变量和方法,共享于所有实例。&quot;==&quot;比较基本类型的值或引用类型的地址,而equals比较对象内容(需重写)。Java只有值传递,对于引用类型传递的是地址副本。String对象不可变,拼接操作会创建新对象而非修改原对象。Java 10的var支持类型推断,Java 16的Record提供不可变类简化。
72 0
|
3月前
|
存储 安全 Java
应届生面试高频 Java 基础问题及实操示例解析
本文总结了Java基础面试中的高频考点,包括数据类型分类、final修饰符的三种用途、static关键字特性、==与equals的区别、Java只有值传递的特性、String的不可变性、Error与Exception的差异、程序初始化顺序规则,以及IO流的字节流/字符流分类。每个问题都配有简明定义和典型示例,如用final修饰变量示例、static方法调用限制说明等,帮助应聘者快速掌握核心概念和实际应用场景。
55 0