18.四数之和
标题链接:https://leetcode-cn.com/problems/4sum/
难度:中等
给定一个包罗 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]]解法一:双指针法 + 排序
解法思绪:
假如做过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还大,都可以直接跳过。
代码: |