目录

AaronJny

诗酒繁华,书剑天涯。

标签: 二分搜索 (1)

leetcode题解第18题 4Sum(四数之和)

跟第 15 题、第 16 题比较相似的一道题,题目大意是说: 给定一个包含 n 个整数的数组 nums 和一个整数 target,从数组中找出所有不重复的四个数相加等于 0 的组合。 注意,仅字典序不同的、包含数字相同的四元组被认为是重复的,只能保留其中一个。 样例输入: nums = [1, 0, -1, 0, -2, 2] target = 0 样例输出: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ] 题目链接:https://leetcode.com/problems/4sum/ 解题思路: 最简单的思路当然是四层循环啦,但不用试,估计也会爆炸 =。= 怎么优化呢?对,还是二分,这几道题一直在考二分 orz... 总共 n 个数,我们可以把它们两两相加,产生一个新的列表。且列表中的每个元素不止保存两个数的和,还要保存这两个数的下标,可以通过类(python)或结构体(c/c++)来实现。 新的列表我们给它起个名字,比方说就叫 sumnums。对 sumnums 进行排序,方便后面使用二分查找。 枚举 sumnums....