两数、三数以及四数之和

2024-04-26 11:04
文章标签 四数

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

两数之和

    给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出和为目标值 target 的那两个整数,并返回它们的数组下标。
    你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
    你可以按任意顺序返回答案。

示例 1:
    输入:nums = [2,7,11,15], target = 9
    输出:[0,1]
    解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
示例 2:
    输入:nums = [3,2,4], target = 6
    输出:[1,2]
示例 3:
    输入:nums = [3,3], target = 6
    输出:[0,1]

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer,Integer> map = new HashMap<>();for(int i = 0;i < nums.length;i++){if(map.get(target - nums[i]) != null){return new int[]{map.get(target - nums[i]), i};}else{map.put(nums[i], i);}}return new int[]{-1, -1};}
}

        这题的思路就是用一个map来保存之前遍历过的元素以元素所对应的下标,这样就可以做到在遍历一边数组的前提下解决这道问题。
        以数组[2,7,11,15],target = 9为例子,首先判断target-nums[i]在不在map中,9-2=7,此时map为空,不进入if,之后将元素2以及对应下标0放入map中,之后遍历到元素7,判断target-nums[i]在不在map中,显然9-7=2,2刚刚被放入map中,此时就得到了一个符合要求的答案,返回map中和元素2对应的下标和当先下标i的组合。
        如果这道题中的给定数组升序排列的,这道题还可以采用双指针来解决,定义left指针指向数组的起始位置,right指针指向数组的末尾位置,如果nums[left] + nums[right] > target,right指针向左移动一次,如果nums[left] + nums[right] < target,left指针向右移动一次,如果left >= right,还没有找到符合nums[left] + nums[right] = target的答案,直接返回[-1, -1]。

三数之和

    给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
    注意:答案中不可以包含重复的三元组。

示例 1:
    输入:nums = [-1,0,1,2,-1,-4]
    输出:[[-1,-1,2],[-1,0,1]]
    解释:
    nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
    nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
    nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
    不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
    注意,输出的顺序和三元组的顺序并不重要。
示例 2:
    输入:nums = [0,1,1]
    输出:[]
    解释:唯一可能的三元组和不为 0 。
示例 3:
    输入:nums = [0,0,0]
    输出:[[0,0,0]]
    解释:唯一可能的三元组和为 0 。

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> ans = new ArrayList<>();Arrays.sort(nums);for(int i = 0;i < nums.length;i++){if(i > 0 && nums[i] == nums[i - 1]) continue;int left = i + 1;int right = nums.length - 1;while(left < right){if(nums[left] + nums[right] + nums[i] > 0){right--;}else if(nums[left] + nums[right] + nums[i] < 0){left++;}else{List<Integer> list = new ArrayList<>();list.add(nums[left]);list.add(nums[right]);list.add(nums[i]);ans.add(list);while(left < right && nums[left] == nums[left + 1]) left++;while(left < right && nums[right] == nums[right - 1]) right--;left++;right--;}}}return ans;}
}

        三数之和的思路有三个指针,分别是i,left和right。由于题目要求不能有重复的三元组,因此三个指针都需要去重,在去重之前,需要对数组进行排序,将相同的元素排在相邻位置,方便去重。i和left指针向右移动,right指针向左移动。基本思路就是每次最外层for选定i指针指向某个元素后,通过left++或right–在[i + 1, nums.length - 1]寻找两数之和等于-nums[i]的下标,其实就是上述说到两数之和,target等于-nums[i]。也就是nums[left]+nums[right] + nums[i] = 0。由于数组升序,可以使用双指针的思路去做,这里的双指针就是left和right。如果nums[left]+nums[right] + nums[i] > 0,则right–。如果nums[left]+nums[right] + nums[i] < 0,则left++。
        以[-1,0,1,2,-1,-4]为例子,说明三数之和的过程。排序之后得到[-4, -1, -1, 0, 1, 2]。if(i > 0 && nums[i] == nums[i - 1])是i指针的去重操作。-4不进入指针i的去重if判断,之后遍历left = i + 1,left指向0,right指向2,nums[i] + nums[left] + nums[right] < 0,left++,left指向-1,nums[i] + nums[left] + nums[right] < 0,left++,left指向-1,nums[i] + nums[left] + nums[right] < 0,left++,left指向0,nums[i] + nums[left] + nums[right] < 0,left++,left指向1,nums[i] + nums[left] + nums[right] < 0,left++,left指向2,不小于right,第一轮for循环结束。
        第二轮for循环,i指向-1,不满足if判断中的nums[i] = nums[i - 1],left = i + 1,left指向-1,right指向2,此时nums[i] + nums[left] + nums[right] = 0,将[-1, -1, 2]保存到ans集合中,之后是对left和right指针进行去重操作,
left指向下标为2的-1,left + 1指向元素0,nums[left] != nums[left + 1],不进入while循环,right也不进入while循环,left++,right–,left指向元素0,right指向元素1,满足nums[i] + nums[left] + nums[right] = 0,将[-1, 0, 1]保存到ans集合中,之后是对left和right指针进行去重操作,不满足left和right都不满足while循环条件,left++,right–,left 不小于right,跳出循环。
        第三轮for循环,i指向了-1,满足if判断中nums[i] = nums[i - 1],continue,因为nums[left]+nums[right] = -1已经在上轮循环中遍历过,因此直接进入第四轮for循环。
        按上述步骤如此重复,就可以得到该题的最终答案。
        在对left和right去重后,还需要再最后对left++一次,对right–一次,原因在于经过while循环后,left,right指向了最后一个重复元素,因此还需要再走一步。还有一个点需要注意的就是对指针i进行去重时,不能使用nums[i] = nums[i + 1]。原因在于left从i + 1开始,如果nums[i] = nums[i + 1]就continue,就说明nums[i] != nums[left]。如[-1, -1, 2]这个例子,如果使用nums[i] = nums[i + 1],则无法得到正确答案,使用nums[i] = nums[i - 1]则可以。

四数之和

    给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复):

  • 0 <= a, b, c, d < n
  • a、b、c 和 d 互不相同
  • nums[a] + nums[b] + nums[c] + nums[d] == target

    你可以按 任意顺序 返回答案 。

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {Arrays.sort(nums);List<List<Integer>> res = new ArrayList<>();for(int k = 0;k < nums.length;k++){if(k > 0 && nums[k] == nums[k - 1]) continue;for(int i = k + 1; i < nums.length;i++){if(i > k + 1 && nums[i] == nums[i - 1]) continue;int left = i + 1;int right = nums.length - 1;while(left < right){long sum = (long) nums[k] + nums[i] + nums[left] + nums[right];if(sum > target) right--;else if(sum < target) left++;else{List<Integer> list = new ArrayList<>();Collections.addAll(list, nums[k], nums[i], nums[left], nums[right]);res.add(list);while(left < right && nums[left] == nums[left + 1]) left++;while(left < right && nums[right] == nums[right - 1]) right--;left++;right--;}}}}return res;}
}

        三数之和和四数之和的求解方法是一样的,相对于三数之和,四数之和多了一个数,仅最外层多了一层循环以及对应的去重逻辑。

这篇关于两数、三数以及四数之和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

第十八题:四数之和

题目描述 给定一个包含 n 个整数的数组 nums 和一个目标值 target,找出 nums 中的四个整数,使得它们的和等于 target。你可以假设每个输入都只有一个解决方案,并且不能使用同一个元素多次。 实现思路 采用排序加双指针的方法来解决这个问题。首先对数组进行排序,然后遍历数组,对于每一个元素,设定一个新的目标值为原目标值减去这个元素的值,再利用三数之和的解法找到剩下的三个数。为

★ 算法OJ题 ★ 力扣18 - 四数之和

Ciallo~(∠・ω< )⌒☆ ~ 今天,爱丽速子将和大家一起做一道双指针算法题--四数之和~ 目录 一  题目 二  算法解析 三  编写算法  做此题前最好先看一下前两篇博客~: ★ 算法OJ题 ★ 力扣 LCR179 - 和为 s 的两个数字-CSDN博客 ★ 算法OJ题 ★ 力扣15 - 三数之和-CSDN博客 一  题目 18. 四数之和 - 力扣(Lee

算法------四数相加 II (java 版本)

题目: 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0。为了使问题简单化,所有的 A, B, C, D 具有相同的长度 N,且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间,最终结果不会超过 2^31 - 1 。例如:输入:A = [

代码随想录 -- 哈希表 -- 四数之和

18. 四数之和 - 力扣(LeetCode) 思路:(与三数之和类似,在外面加一层循环)         1. 先将 nums 按升序排序         2. 初始状态:k = 0,i = k+1,left = i+1,right = len(nums)-1         3. 进入第一层 for 循环:         如果 nums[k]>0 and target>0 and

学习记录:js算法(十六):四数之和

文章目录 四数之和我的思路 总结 四数之和 给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。 请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复): 0 <= a, b, c, d < na、b、c 和 d 互不相同nums[a]

Leetcode 18-四数之和

题解看代码随想录 /* 1.先排序,为了便于使用双指针,复杂度O(logN) 2.固定最小指针a,b,双指针c和d分别从0和len-1向中间移动 从两端向中间移动是为了使得两个数下标不重合,且可以将时间复杂度从双重循环的O(N4)降到O(N3) 3.终止条件:a>N-3||nums[a]>0(此时四数之和必定大于0) 3.不可以包含重复元素:前后元素相同时跳过 */ class Solution

代码随想录算法训练营第六天|454.四数相加II;383. 赎金信;15. 三数之和;18. 四数之和

今日任务 ●  454.四数相加II ●  383. 赎金信 ●  15. 三数之和 ●  18. 四数之和 详细布置 454.四数相加II 建议:本题是 使用map 巧妙解决的问题,好好体会一下 哈希法 如何提高程序执行效率,降低时间复杂度,当然使用哈希法 会提高空间复杂度,但一般来说我们都是舍空间 换时间, 工业开发也是这样。 题目链接:. - 力扣(LeetCode) 题目链接/文

算法008:四数之合

四数之和. - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/4sum/description/ 在前面的两个题中,我们已经完成了两数之和和三数之和,到本题四数之和,其实也只是前几个题的延伸,在三数之和的基础上再固定一个数字。 先固定一个数字,剩下三个数按照三数之和的方

day07--454.四数相加II+383. 赎金信+ 15. 三数之和+ 18. 四数之和

一、454.四数相加II 题目链接:https://leetcode.cn/problems/4sum-ii/ 文章讲解:https://programmercarl.com/0454.%E5%9B%9B%E6%95%B0%E7%9B%B8%E5%8A%A0II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE 视频讲解:https://www

代码随想录算法训练营第七天| 454.四数相加II |383. 赎金信 |15. 三数之和 |18. 四数之和

454.四数相加II 文档讲解:代码随想录 视频讲解:学透哈希表,map使用有技巧!LeetCode:454.四数相加II_哔哩哔哩_bilibili 1. 暴力算法。 2. 先两个循环将和放到map中,再两个循环求和查询map,计算总数求和,将一个4层循环复杂度降低了。要查找一个元素是否出现用map, map也是一个hash结构。 3.没啥问题。 4. 用了半个小时左右。 38