力扣第18题. 四数之和

2024-04-16 23:12
文章标签 力扣 18 四数

本文主要是介绍力扣第18题. 四数之和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:

给定一个包含 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] ]

Python3解答代码:

class Solution:def fourSum(self, nums: List[int], target: int) -> List[List[int]]:# 排序nums数组nums.sort()# 初始化变量,初始化一个空列表result用于存储结果n = len(nums)result = []# 循环每个可能作为四元组的第一个数字nums[i]for i in range(n):# 如果 nums[i] 大于 target 并且都为正数,后续元素只会更大,就可以提前结束当前循环,# 因为不可能存在四个数的和等于 targetif nums[i] > target and nums[i] > 0 and target > 0:break# 第一层循环中的元素 nums[i],如果当前元素与前一个元素相同,则直接跳过,避免重复计算if i > 0 and nums[i] == nums[i-1]:continue# 内层循环遍历每个可能作为四元组第二个数字的 nums[j]for j in range(i+1, n):if nums[i] + nums[j] > target and target > 0:break# 跳过相同的 nums[j] 值以避免重复的四元组。if j > i+1 and nums[j] == nums[j-1]:continue# 确定两个数之后,使用双指针来查找后两个数,使得四数之和等于target、left,right = j+1, n-1while left < right:# 计算选中的四个数之和ss = nums[i] + nums[j] + nums[left] + nums[right]if s == target:result.append([nums[i], nums[j], nums[left], nums[right]])# 为了避免重复的四元组,需要移动left和right来跳过重复的元素# 只要 left 指向的元素与其右边相邻的元素相同,就继续向右移动 left 指针while left < right and nums[left] == nums[left+1]:left += 1# 只要 right 指向的元素与其左边相邻的元素相同,就继续向左移动 right 指针while left < right and nums[right] == nums[right-1]:right -= 1# 完成上述循环后,需要将 left 和 right 分别再向中间移动一位,# 以避免重复计算当前的组合left += 1right -= 1#  四数之和小于目标值,需要将left指针向右移动elif s < target:left += 1# 四数之和大于目标值,为了减少和的大小# 需要将 right 指针向左移动,即向更小的数移动else:right -= 1return result

上述代码实现过程解析:

上述代码实现了在给定整数数组 nums 中找出所有四个元素的组合,使得它们的和等于目标值 target。下面是代码的详细解释:

  1. 排序数组:首先,对输入的整数数组 nums 进行排序。这样做的目的是为了在后续的处理中能更方便地进行去重和剪枝操作。

  2. 初始化变量:获取数组的长度 n,并初始化一个空列表 result 用于存储结果。

  3. 遍历数组:使用两层循环遍历数组,首先固定两个数 nums[i]nums[j],其中 ij 分别表示第一层循环和第二层循环的索引。这两个数将作为四个元素中的前两个。

  4. 剪枝操作:在第一层循环中,有两处剪枝操作:

    • 如果当前的 nums[i] 大于 target 并且都为正数,就可以提前结束当前循环,因为后续元素只会更大,不可能满足条件。
    • 在第二层循环中,如果当前的 nums[i] + nums[j] 大于 target 并且 target 为正数,同样可以提前结束当前循环。
  5. 去重操作:**在每一层循环中,都需要进行去重操作,以避免重复的组合被计算。具体做法是:

    • 对于第一层循环中的元素 nums[i],如果当前元素与前一个元素相同,则直接跳过,避免重复计算。
    • 对于第二层循环中的元素 nums[j],如果当前元素与前一个元素相同,则直接跳过,避免重复计算。
  6. 双指针法找到剩余两个数:**在固定了前两个数后,剩余的两个数采用双指针法。定义两个指针 leftright 分别指向当前范围内的最左和最右的元素。然后循环移动这两个指针,不断调整它们指向的元素,直到找到符合条件的组合或者两个指针相遇。

  7. 判断条件和更新指针:

    • 如果四个数的和等于目标值 target,则将这个组合添加到结果列表 result 中,并同时更新指针 leftright,以避免重复计算相同的组合。
    • 如果四个数的和小于目标值 target,则将左指针 left 右移一位。
    • 如果四个数的和大于目标值 target,则将右指针 right 左移一位。
  8. 返回结果:最终返回结果列表 result,其中存储了所有满足条件的四个元素的组合。

重难点解释:

1.剪枝操作:

"剪枝"指的是在搜索过程中通过一些条件判断提前结束不必要的搜索分支,从而减少搜索空间,提高算法效率。具体来说,这段代码中的剪枝操作有两个地方:

  1. 在第一层循环和第二层循环中,通过比较当前元素与目标值的大小关系,如果可以确定后续元素无法满足条件,就提前结束当前循环。例如,在第一层循环中,如果 nums[i] 大于 target 并且都为正数,后续元素只会更大,就可以提前结束当前循环,因为不可能存在四个数的和等于 target

  2. 在第二层循环中,通过比较当前两个元素的和与目标值的大小关系,同样可以提前结束当前循环。如果 nums[i] + nums[j] 大于 target 并且 target 为正数,后续元素只会更大,也可以提前结束当前循环。

2.if j > i+1 and nums[j] == nums[j-1]: continue 解释为啥是i+1

这段代码的意图是在固定了第一个数字 nums[i] 后,跳过那些可能会导致重复四元组的第二个数字 nums[j]。这里的逻辑是:

  • j > i+1:这个条件用于确保 j 不仅仅是在 i+1 的位置上,也就是说,j 应该至少是从 i+2 的位置开始考虑。这是因为:

    • j == i+1 时,nums[j] 是在 nums[i] 后面的第一个元素,此时没有前一个元素 nums[j-1] 与之相比较,因此不需要进行去重判断。
    • j > i+1 时,表示 j 至少是第三个考虑的元素,此时 nums[j-1] 存在,并且位于 nums[j] 之前,因此可以进行重复检查。
  • nums[j] == nums[j-1]:这个条件检查当前的元素 nums[j] 是否与它前一个元素 nums[j-1] 相等。如果相等,说明使用当前的 nums[j] 可能会生成与前一个循环相同的四元组,因此应该跳过当前的 nums[j]

目的和重要性

  • 防止重复结果:如果不进行这样的去重,相同的 nums[j] 值将在内层循环中多次使用,与同一个 nums[i] 结合,可能会导致生成重复的四元组。
  • 提高效率:通过跳过重复元素,可以减少不必要的计算和迭代,这对于处理大数据集时尤为重要。

3.核心代码解释:

if nums[i] + nums[j] > target and target > 0:break

限制 target > 0 的原因主要是为了确保当目标值 target 是正数时,这个剪枝逻辑才会生效。这样的条件设定对于整体算法的正确性和效率都有影响,以下是几个关键点:

1. 保证剪枝的适用性

target 是正数时,如果两个数的和已经超过了 target,继续在正数范围内添加更多的数会使得总和进一步增加,从而不可能等于 target。这个逻辑在 target 是正数时显然有效。

2. 处理负数情况

如果 target 是负数或零,上述剪枝条件可能不适用,因为:

  • target 是零或负数时,可能需要包括负数在内的组合来达到 target。即使当前的两数之和已经超过了 target,通过选择负数作为其他组成部分,仍然有可能将总和调整至 target
  • 对于负 target,若当前两数之和大于 target,但它们之间存在足够大的负数,这些负数仍然可以使得最终的四数之和等于 target

3. 避免不必要的逻辑应用

如果不加 target > 0 这个条件,那么对于负数 targettarget 为零的情况,剪枝可能导致漏掉有效的解。例如,假设 target = -10,如果仅仅因为两个正数的和大于 -10 就停止搜索,可能会错过一些包含负数且其和为 -10 的有效组合。

解释一下这个几句代码的实现:

 while left < right and nums[left] == nums[left+1]:left += 1while left < right and nums[right] == nums[right-1]:right -= 1left += 1right -= 1elif s < target:left += 1else:right -= 1return result

代码位于双指针搜索的环节,用于在已经固定了两个数字之后,在数组的剩余部分中寻找两个数,使得这四个数的和等于给定的目标 target。这一部分是通过移动左指针 left 和右指针 right 来实现的。下面是详细的逻辑解释:

判断当前四数之和 s

s = nums[i] + nums[j] + nums[left] + nums[right]

首先计算当前选定的四个数的和 s,并将其与目标 target 进行比较。

判断三种情况

  • 四数之和等于目标值 (s == target)

    • 将符合条件的四元组 [nums[i], nums[j], nums[left], nums[right]] 添加到结果列表 result 中。

    • 接下来,为了避免重复的四元组,需要移动 leftright 指针来跳过所有相同的元素。

    • while left < right and nums[left] == nums[left+1]:left += 1
      while left < right and nums[right] == nums[right-1]:right -= 1
      left += 1
      right -= 1
      

      • 这两个 while 循环分别用于:

      • 完成上述循环后,需要将 leftright 分别再向中间移动一位,以避免重复计算当前的组合。
      • 跳过右边重复的元素:只要 right 指向的元素与其左边相邻的元素相同,就继续向左移动 right 指针。
      • 跳过左边重复的元素:只要 left 指向的元素与其右边相邻的元素相同,就继续向右移动 left 指针。
  • 四数之和小于目标值 (s < target)

    • 为了增加和的大小,需要将 left 指针向右移动,即向更大的数移动。

      • left += 1

  • 四数之和大于目标值 (s > target)

    • 为了减少和的大小,需要将 right 指针向左移动,即向更小的数移动。

right -= 1

 综上,本文的对于力扣18. 四数之和的Python3解答,仅仅是个人学习资料记录,也十分高兴我的见解可以帮助其他的正在做这个题目的同学,基础较差,仅仅是个人见解,大神勿喷,欢迎交流,谢谢!

这篇关于力扣第18题. 四数之和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/910162

相关文章

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们在map中能够找到这个差值,就说明存在两个整数的和为目标值。 如果没有找到,就将当前循环的nums[i]以及下标i放入map中,以便后续查

力扣第347题 前K个高频元素

前言 记录一下刷题历程 力扣第347题 前K个高频元素 前K个高频元素 原题目: 分析 我们首先使用哈希表来统计数字出现的频率,然后我们使用一个桶排序。我们首先定义一个长度为n+1的数组,对于下图这个示例就是长度为7的数组。为什么需要一个长度为n+1的数组呢?假如说总共有三个数字都为1,那么我们需要把这个1放在数组下标为3的位置,假如说数组长度为n,对于这个例子就是长度为3,那么它的

react笔记 8-18 事件 方法 定义方法 获取/改变数据 传值

1、定义方法并绑定 class News extends React.Component {constructor(props) {super(props)this.state = {msg:'home组件'}}run(){alert("我是一个run") //方法写在类中}render() {return (<div><h2>{this.state.msg}</h2><button onCli

【数据结构与算法 | 灵神题单 | 删除链表篇】力扣3217, 82, 237

总结,删除链表节点问题使用到列表,哈希表,递归比较容易超时,我觉得使用计数排序比较稳,处理起来也不是很难。 1. 力扣3217:从链表中移除在数组中的节点 1.1 题目: 给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后,返回修改后的链表的头节点。 示例 1: 输入: nums = [1,2,3], head = [1,2,3,

力扣 739. 每日温度【经典单调栈题目】

1. 题目 理解题意: 1.1. 给一个温度集合, 要返回一个对应长度的结果集合, 这个结果集合里面的元素 i 是 当前 i 位置的元素的下一个更高温度的元素的位置和当前 i 位置的距离之差, 若是当前元素不存在下一个更高温度的元素, 则这个位置用0代替; 2. 思路 本题用单调栈来求解;单调栈就适用于来求当前元素左边或者右边第一个比当前元素大或者小的元素;【单调栈:让栈中的元素保持单调

力扣接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: 输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]输出:6解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 示例 2: 输入:height

每日一题,力扣leetcode Hot100之238.除自身以外数组的乘积

乍一看这个题很简单,但是不能用除法,并且在O(N)时间复杂度完成或许有点难度。 考虑到不能用除法,如果我们要计算输出结果位置i的值,我们就要获取这个位置左边的乘积和右边的乘积,那么我新设立两个数组L和R。 对于L来说,由于表达的是位置i左边的数的乘积,那么L[0]=1,因为第一个数字左边没数那么为了不影响乘积初始值就设置为1,那么L[1]=L[0]*nums[0],那么L[i]=L[i-1

力扣 797. 所有可能路径【DFS】

1. 题目 2. 代码 DFS , 直接见代码 class Solution {public:vector<int> path;vector<vector<int>> res; // 结果集void dfs(vector<vector<int>>& graph, int cur, int n){// 找出所有从节点 0 到节点 n-1 的路径// 下标从 0 开始的if (

Day18_0.1基础学习MATLAB学习小技巧总结(18)——MATLAB绘图篇(1)

利用空闲时间把碎片化的MATLAB知识重新系统的学习一遍,为了在这个过程中加深印象,也为了能够有所足迹,我会把自己的学习总结发在专栏中,以便学习交流。 参考书目:《MATLAB基础教程 (第三版) (薛山)》 之前的章节都是基础的数据运算用法,对于功课来说更加重要的内容是建模、绘图、观察数据趋势,接下来我会结合自己的使用经验,来为大家分享绘图、建模使用的小技巧。 二维图形绘制 在本章开

18. 4 Sum

题目: 解答: 与之前的三数之和的解法类似,也是先排序,然后不断剔除不可能的条件,最后两个参数,通过两头求和计算得出。 代码: class Solution {public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> result;int len = nums.size