18.四数之和

分享
源码 2024-9-26 16:53:51 151 0 来自 中国
18.四数之和

标题链接:https://leetcode-cn.com/problems/4sum/
难度:中等
给定一个包罗 n 个整数的数组 nums 和一个目的值 target,判定 nums 中是否存在四个元素 a,b,cd ,使得 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]]解法一:双指针法 + 排序

解法思绪:
假如做过15. 三数之和会发现这两个题是一个解题思绪。
我们利用一个双重循环a和b来控制四个数中最小的两数,再用双指针l和r来控制别的两数。
盘算:sum = nums[a]+nums+nums[l]+nums[r];
若sum == target,则把这四个数添加到结果数组中
若sum > target,则阐明r太大了,将r--,将指针r向左移动。
若sum < target,则阐明l太大了,将l++,将指针l向右移动。
办理重复结果题目:
我们在四层变量值改变的时间,可以判定一下,是否和上一次的值相称,若相称,直接跳过这次循环。
时间复杂度优化:
我们在外两层a和b变量值改变的时间,可以盘算一下,他们的最大值和最小值,若最大值比target还小,或者最小值比target还大,都可以直接跳过。
1.png 代码:
您需要登录后才可以回帖 登录 | 立即注册

Powered by CangBaoKu v1.0 小黑屋藏宝库It社区( 冀ICP备14008649号 )

GMT+8, 2025-2-2 13:51, Processed in 0.183549 second(s), 35 queries.© 2003-2025 cbk Team.

快速回复 返回顶部 返回列表