让别人做网站是要每年续费吗,东莞网站推广营销网站设计,可以做淘宝推广的网站有哪些内容,wordpress 最简单模板文章目录 前言一、两数之和1, 题目2, 思路分析3, 代码展示 前言 各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: #x1f4d5; JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等 #x1f4d7; Java数据结构: 顺序表, 链表… 文章目录 前言一、两数之和1, 题目2, 思路分析3, 代码展示 前言 各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等 Java数据结构: 顺序表, 链表, 堆, 二叉树, 二叉搜索树, 哈希表等 JavaEE初阶: 多线程, 网络编程, TCP/IP协议, HTTP协议, Tomcat, Servlet, Linux, JVM等(正在持续更新) 一、两数之和
1, 题目
OJ链接
题目给定的数组保证有序, 并且需求是查找 查找的本质是排除 ! ! 查找的本质是排除 ! ! 查找的本质是排除 ! ! 有序的数组成单调性, 能很方便的使用双指针 2, 思路分析
最简单的暴力枚举 : 两层 for 循环, 从先固定一个数, 再依次遍历第二个数, 判断这两个数的和是否为 targer(目标值), 时间复杂度为O(N²), 会超出时间限制
既然暴力枚举不行, 那尝试就使用双指针 根据实际情况分析选择对撞双指针还是快慢双指针, 本题要求在数组中查找, 那么使用对撞双指针能很大程度上提高效率 而且刚才标注了一句话 : 查找的本质是排除, 查找的本质是排除, 查找的本质是排除 ! ! !
如果每次判断, 都能尽可能多的排除数据, 就能尽可能地提高效率
解题步骤 :
定义 left 指针在 0 下标, 定义 right 指针在 nums.length - 1 下标left 的值 right 的值, 和 target 比较如果二者之和等于 target , 即为所求 如果二者之和大于 targer, 令 right-- (这一步就是在排除) 如果二者之和小于 targret, 令 left (这一步就是在排除) 如何理解利用数组单调性, 双指针能够高效的排除 ? 如果数组不是单调的, 不能保证 10 后面的数一定比 10 大, 就不能排除了 3, 代码展示 public int[] twoSum(int[] nums, int target) {int left 0;int right nums.length - 1;while(left right) {if(nums[left] nums[right] target) {right--;}else if(nums[left] nums[right] target){left;}else {return new int[]{nums[left],nums[right]};}}return nums;}
