LeetCode: 18. 4Sum

引言

题目链接:https://leetcode.com/problems/4sum/description/

题目大意

给出一个包含n个整数的数组nums以及一个目标值target,这个数组是否存在有元素a,b,c,d使得 a + b + c + d = target,找出所有满足条件的a,b,c,d的组合

  • Example

题解

这题其实是第15题的变种,相信看了这篇题解举一反三很容易能拿下这题,LeetCode:15.3Sum题解,Click Here!

这道题由于是求4个数的目标值,所以需要滚动查询的数字由15题的两个变成了3个,很暴力的一个方法,在原来的循环上再加一层循环,内部继续再剩余数组上枚举两个数求和即可

Hint:

如何优雅的避免重复也是一个坑,外层两个循环都需要判断下当前选取的数字和上一次是不是相同的,相同的直接跳过,内层俩数字枚举时2也注意判断即可(千万别忘了某一层少写了这个条件,不然美滋滋~)

复杂度

时间复杂度 O(n^3)

空间复杂度 O(1)

AC代码

c++版本

go版本

繁夜

发表评论


:[斜眼笑]::[喷血]::[无奈]::[托腮]::[小纠结]::[卖萌]::[撇嘴]::[色]::[发呆]::[得意]::[流泪]::[尴尬]::[发怒]::[调皮]::[呲牙]::[惊讶]::[难过]::[冷汗]::[偷笑]::[可爱]::[白眼]::[傲慢]::[困]::[流汗]::[憨笑]::[大兵]::[奋斗]::[疑问]::[嘘...]::[晕]::[衰]::[骷髅]::[敲打]::[再见]::[擦汗]::[抠鼻]::[鼓掌]::[糗大了]::[坏笑]::[哈欠]::[鄙视]::[委屈]::[阴险]::[亲亲]::[吓]::[可怜]::[笑哭]::[doge]::[泪奔]::[羊驼]::[幽灵]::[OK]::[勾引]::[强]::[爱心]::[心碎]::[喝彩]::[玫瑰]::[棒棒糖]::[钞票]::[咖啡]::[菜刀]::[炸弹]::[手枪]::[药]:

刷新评论