Leetcode-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]
]

解题思路为找到所有不重复的满足a+b+c+d=target的四个数,为了做到不重复,首先可以用排序的方式来避免重复

可以将原数组按照非递减的顺序进行排序,再顺序查找a,b,c,d,哈希表可以加速查询的速度,同时也是可以统计每个数出现的次数。

以数组nums = [1, 0, -1, 0, -2, 2]为例,则

 

In [1]:
nums = [1, 0, -1, 0, -2, 2]
In [4]:
from collections import Counter
In [2]:
res=[]
In [5]:
dic = Counter(nums)
In [6]:
dic
Out[6]:
Counter({1: 1, 0: 2, -1: 1, -2: 1, 2: 1})
In [7]:
arr = sorted(dic.keys())
In [8]:
arr
Out[8]:
[-2, -1, 0, 1, 2]
 

接着是嵌套便利,最外层遍历到什么地方,就将对应的数的个数-1,然后在内层循环里也把选择的数的数量-1,如果这个数已经没了,那么就用continue跳过。

四数之和和三数之和的差别在于,第二个数选择的时候要 -1,最内层循环结束以后还要 +1,因为之后最外层的 a 也会再遍历到这个位置。

总代码如下

from collections import Counter
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        res = []
        dic = Counter(nums) #对每个数出现的次数进行统计
        arr = sorted(dic.keys())  #排序键值
        for i, a in enumerate(arr):
            dic[a] -= 1 #a用掉了一次,而且a的位置之后不会再遍历到了,不需要加回
            for j, b in enumerate(arr[i:]):  #从arr[i]开始找b的值
                if dic[b] < 1: #b可能等于a,判断一下,如果dic[b]不够1个,跳过这次循环
                    continue
                dic[b] -= 1
                for c in arr[i+j:]:  #从arr[i+j]开始找c的值,注意上一层循环枚举j以后,需要再加最外层的i
                    if dic[c] < 1: #同上层循环b的判断
                        continue
                    d = target - (a + b + c)  
                    if d < c:   #因为是非递减顺序,如果d小于c,就直接跳出,这样就可以避免重复
                        break
                    if (d == c and dic[d] > 1) or (d > c and dic[d] > 0):
                        res.append([a, b, c, d])
                dic[b] += 1 #b现在所处的位置,之后a还会遍历到,因此需要加回1
        return res

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇