网站建设的业务规划,wordpress不同背景,域名和网站一样吗,2021国外免费服务器文章目录 前言一、四数之和1, 题目2, 思路分析3, 代码 前言 各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: #x1f4d5; JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等 #x1f4d7; Java数据结构: 顺序表, 链表, 堆… 文章目录 前言一、四数之和1, 题目2, 思路分析3, 代码 前言 各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等 Java数据结构: 顺序表, 链表, 堆, 二叉树, 二叉搜索树, 哈希表等 JavaEE初阶: 多线程, 网络编程, TCP/IP协议, HTTP协议, Tomcat, Servlet, Linux, JVM等(正在持续更新) 一、四数之和
1, 题目
OJ链接
这题是在三数之和的基础上进行了一些提升, 而三数之和又是在两数之和的基础上的提升, 核心算法思想是一致的, 不熟悉 “两数之和” 这道题的小伙伴建议看一下 这篇文章 , 不熟悉 “三数之和” 这道题的小伙伴建议看一下 这篇文章 , 弄懂了前两道题, 做出本题会非常轻松 2, 思路分析
最简单的暴力枚举 : 四层 for 循环, 从先固定一个数, 在剩余区间上固定一个数, 再在剩余区间上固定一个数, 暴力枚举依次找第四个数, 判断这四个数的和是否为 0 (目标值), 时间复杂度为O(N⁴), 必然会超出时间限制
先对数组排序(有序后使用对撞双指针可以大大提高效率)使用 k 指针先固定一个数在剩余区间上使用 “三数之和” 的解法找到另外三个数 固定住 k 时, 三数之和的总和定义为 threeTarget target - nums[k], 固定住 i 时, 两数之和的总和定义为 twoTarget threeTarget - nums[i] 总之就是, 四数之和中基本可以复用三数之和的代码, 而三数之和中又复用了两数之和的代码 三数之和中, 需要对 i, left, right 去重, 本题多了一个对 k 的去重, 去重方式和 i 的去重方式一致 当 k 指向 0 下标, i 指向 1 下标时, left 和 right 指针已经在剩余区间上遍历完了所有四元组, 接下来 k 不要着急自增, 因为 i 还没有遍历完(三数之和还没有执行完), 应该让 i 自增, left 回到 i 1 位置开始, 继续执行未完成的三数之和
后续流程就不再赘述了, 就是把三数之和的代码放在 k 的循环之中, 稍作修改即可 3, 代码 public ListListInteger fourSum(int[] nums, int target) {ListListInteger list new ArrayList();Arrays.sort(nums);int k 0;// k 的循环while(k nums.length - 3){long threeTarget target - nums[k];int i k 1;// i 在剩余区间上执行三数之和while(i nums.length - 2) {long twoTarget threeTarget - nums[i];int left i 1;int right nums.length - 1;// left 和 right 在剩余区间上执行两数之和(对撞双指针)while(left right) {ListInteger inList new ArrayList();if(nums[left] nums[right] twoTarget) {right--;}else if(nums[left] nums[right] twoTarget) {left;}else {// left 和 right 的去重while(left right nums[right] nums[right - 1]) {right--;}while(left right nums[left] nums[left 1]){left;}inList.add(nums[k]);inList.add(nums[i]);inList.add(nums[left]);inList.add(nums[right]);list.add(inList);left;right--;}}// i 的去重i;while(nums[i] nums[i - 1] i nums.length - 2) {i;}}// k 的去重k;while(nums[k] nums[k - 1] k nums.length - 3) {k;}}return list;}
