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

代码随想录算法训练营第十二天|第18题. 四数之和

文档讲解:代码随想录

难度:有一点点难度

附:寒假继续开始刷题更新刷题记录

passion!!!passion!!!passion!!!

第18题. 四数之和

力扣题目链接(opens new window)

题意:给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。

注意:

答案中不可以包含重复的四元组。

示例: 给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。 满足要求的四元组集合为: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

思路

可以将问题简单化:往期刷过两数之和和三数之和,所以可以尝试将四数之和转换为三数之和,三数之和的解题的一个巧妙思路如下:

为了降低时间复杂程度,可以对一些可以直接排除的元素进行去除:三数之和中如果一个数字大于目标数字,则可以直接去除(由于已知目标是0,故第一个数字不可以大于目标数字)

详细参考以下文档:

代码随想录

第15题. 三数之和

也可以参考本人往期作品中的“三数之和”

代码随想录算法训练营第十一天|383. 赎金信, 15. 三数之和

  1.  由于题目并没有表明该数组是有序k数组,故应先对数组进行排序(sort方法);
  2. 进入循环1.1(k)
  3. 同理,对一些元素直接排除:因为目标的大小正负未知,故应该加一些条件:如果一个数字大于目标,但为了避免出现特殊情况(如num[k]=-4,目标是-10,)应该对该数字和目标进行正负分析并添加验证条件,可以判断   目标数字或num[k]的正负, 最后为代码实现为nums[i] > target && (nums[i] >=0 || target >= 0)
  4. 去除相同的数字(题目要求),因为已经进行了排序,故判断该数字的前(后)即可
  5. 进入循环2.1(i)(2代表为内层,.1代表是内层第一次循环,以下同理)
  6. 进行第二次进入步骤2,3(可以理解为将前两个数字和并为一个整体后,再进行一次判断)
  7. 设置左右指针,左指针为i的下一个元素,右指针为num数组的最后一个元素
  8. 进入循环3.1(判断条件为右指针应该大于左指针)
  9. 求四数之和:sum=num[k]+num[i]+num[left]+num[right],如果sum偏大则将右指针左移动(排序后,右侧数大于左侧),如果sum偏小则将左指针右移动,如果符合则将num[k],num[i],num[left],num[right]计入result数组
  10. 进入循环4.1,4.2再次进行步骤4进行去重
  11. 左右指针都向中移动
  12. 所有循环结束返回result数组
  13. 定义测试部分:

补充

 在Java中,foreach循环也被称为增强型for循环。它可以用来遍历数组、集合或其他类似结构的数据。foreach循环的语法如下:

  for (element_type element : collection) {

  // 循环体

  }

  其中,element_type是集合中元素的类型,element是集合中每个元素的变量名,collection是需要遍历的集合。在循环体中,可以使用element变量来访问当前元素的值。

  下面是一个示例,展示了如何使用foreach循环来遍历一个整型数组:

  int[] numbers = {1, 2, 3, 4, 5};

  for (int number : numbers) {

  System.out.println(number);

  }

  在这个示例中,我们定义了一个整型数组numbers,然后使用foreach循环来遍历这个数组,并在循环体中打印出每个元素的值。输出结果如下:

  除了数组,foreach循环还可以用于遍历其他类型的集合,例如List、Set、Map等。不过需要注意的是,对于Map类型的集合,foreach循环只能遍历其中的键或值,而不能同时访问键和值。

代码如下: 

import java.util.*;

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);  // 排序数组
        List<List<Integer>> result = new ArrayList<>();  // 放结果
        for (int k = 0; k < nums.length; k++) {
            // 剪枝处理
            if (nums[k] > target && nums[k] >= 0) {
                break;
            }
            // 去除nums[k]相同的元素
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.length; i++) {
                // 第二级剪枝
                if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
                    break;
                }
                // 去除nums[i]相同的元素
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = nums.length - 1;
                while (right > left) {
                    long sum = (long) nums[k] + nums[i] + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[k], nums[i], nums[left], nums[right]));
                        // 对nums[left]和nums[right]去重
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;
                        right--;
                        left++;
                    }
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;
        List<List<Integer>> results = solution.fourSum(nums, target);
        for (List<Integer> result : results) {
            System.out.println(result);
        }
    }
}

原文地址:https://blog.csdn.net/lcy57__/article/details/145143913
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/503514.html

相关文章:

  • VS Code AI开发之Copilot配置和使用详解
  • Java - WebSocket
  • MySQL配置my.ini文件
  • 【云岚到家】-day03-门户缓存实现实战
  • Linux 高级路由与流量控制-用 tc qdisc 管理 Linux 网络带宽
  • Vue3 nginx 打包后遇到的问题
  • golang之数据库操作
  • ctf竞赛
  • VirtualBox环境中vscode报错:提取扩展时出错。Failed to fetch
  • Steam个人开发者注册备记
  • 解锁未来情感科技:AI 机器人 Ropet 搭载的前沿智能黑科技
  • K8s数据存储之详解(Detailed Explanation of K8s Data Storage)
  • 【JVM-2.2】使用JConsole监控和管理Java应用程序:从入门到精通
  • latex 中不要求显示页码
  • (一)QSQLite3库简介
  • 平台介绍-快速开发上手指南
  • 快速、可靠且高性价比的定制IP模式提升芯片设计公司竞争力
  • MCANet: 基于多模态字幕感知的大语言模型训练无关视频异常检测
  • 【向量数据库 Milvus】centos8源码安装和部署 Milvus 2.5.3
  • 惯性动作捕捉设备制作动画:打破传统动画制作模式,提高动画制作效率
  • Python 标准库:time——时间的访问和转换
  • MySQL社区版下载及其环境配置(msi)
  • 嵌入式Linux之基于TCP协议的程序
  • 配置Allure环境变量【macOS版】
  • 麒麟系统设置tomcat开机自启动
  • Unity-Mirror网络框架-从入门到精通之RigidbodyPhysics示例