4Sum

題目鏈接

題意

給定一個包含 n 個整數(shù)的數(shù)組 nums 和一個目標(biāo)值 target锋恬,判斷 nums 中是否存在四個元素 a也物,b痢畜,c 和 d ,使得 a + b + c + d 的值與 target 相等锤灿?找出所有滿足條件且不重復(fù)的四元組。

注意點
  1. 如何使得結(jié)果不重復(fù)辆脸?
  2. 如何以O(n^2)的復(fù)雜度求解但校?
解答

??假設(shè)滿足等式的下標(biāo)分別為1st,2st啡氢,3st状囱,4st,且依次遞增倘是。我們先用二重循環(huán)遍歷所有可取的1st和2st亭枷,再判斷是否存在對應(yīng)的3st和4st滿足:nums[1st]+nums[2st]=target-(nums[1st]+nums[2st])為避免超時,必須在常數(shù)時間內(nèi)完成尋找3st和4st搀崭。設(shè)0<a<l-1, a<b<l叨粘,以nums[a]+nums[b]為鍵,數(shù)組[a,b]為值瘤睹,建立哈希表升敲。于是,對于給定的 1st 和 2st轰传,若哈希表中存在對應(yīng)鍵驴党,從鍵值中找到符合要求的[a,b],[1st, 2st, a, b]即為一個解获茬。

??執(zhí)行以上步驟前港庄,還需先將nums排序,便于避免重復(fù)的元素被遍歷恕曲。

Python代碼
class Solution:
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        hash1 = dict()
        nums = sorted(nums)

        add2 = [[-1] * len(nums) for i in range(len(nums))]

        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                add2[i][j] = nums[i] + nums[j]
                hash1[add2[i][j]] = []
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                hash1[add2[i][j]].append([i, j])
        res = []
        pre_f = None

        for first in range(len(nums) - 3):
            if nums[first] == pre_f:
                continue
            pre_f = nums[first]

            pre_s = None
            for second in range(first + 1, len(nums) - 2):
                if nums[second] == pre_s:
                    continue
                pre_s = nums[second]

                t = target - nums[first] - nums[second]
                if t not in hash1:
                    continue
                candidate = hash1[t]
                pre_t = None
                for item in candidate:
                    if item[0] <= second or nums[item[0]] == pre_t:
                        continue
                    pre_t = nums[item[0]]
                    res.append([nums[first], nums[second], nums[item[0]], nums[item[1]]])

        return res
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末鹏氧,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子码俩,更是在濱河造成了極大的恐慌度帮,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,681評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件稿存,死亡現(xiàn)場離奇詭異笨篷,居然都是意外死亡,警方通過查閱死者的電腦和手機瓣履,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評論 3 399
  • 文/潘曉璐 我一進(jìn)店門率翅,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人袖迎,你說我怎么就攤上這事冕臭∠倭溃” “怎么了?”我有些...
    開封第一講書人閱讀 169,421評論 0 362
  • 文/不壞的土叔 我叫張陵辜贵,是天一觀的道長悯蝉。 經(jīng)常有香客問我,道長托慨,這世上最難降的妖魔是什么鼻由? 我笑而不...
    開封第一講書人閱讀 60,114評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮厚棵,結(jié)果婚禮上蕉世,老公的妹妹穿的比我還像新娘。我一直安慰自己婆硬,他們只是感情好狠轻,可當(dāng)我...
    茶點故事閱讀 69,116評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著彬犯,像睡著了一般向楼。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上谐区,一...
    開封第一講書人閱讀 52,713評論 1 312
  • 那天蜜自,我揣著相機與錄音,去河邊找鬼卢佣。 笑死,一個胖子當(dāng)著我的面吹牛箭阶,可吹牛的內(nèi)容都是我干的虚茶。 我是一名探鬼主播,決...
    沈念sama閱讀 41,170評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼仇参,長吁一口氣:“原來是場噩夢啊……” “哼嘹叫!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起诈乒,我...
    開封第一講書人閱讀 40,116評論 0 277
  • 序言:老撾萬榮一對情侶失蹤罩扇,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后怕磨,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體喂饥,經(jīng)...
    沈念sama閱讀 46,651評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,714評論 3 342
  • 正文 我和宋清朗相戀三年肠鲫,在試婚紗的時候發(fā)現(xiàn)自己被綠了员帮。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 40,865評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡导饲,死狀恐怖捞高,靈堂內(nèi)的尸體忽然破棺而出氯材,到底是詐尸還是另有隱情,我是刑警寧澤硝岗,帶...
    沈念sama閱讀 36,527評論 5 351
  • 正文 年R本政府宣布氢哮,位于F島的核電站,受9級特大地震影響型檀,放射性物質(zhì)發(fā)生泄漏冗尤。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,211評論 3 336
  • 文/蒙蒙 一贱除、第九天 我趴在偏房一處隱蔽的房頂上張望生闲。 院中可真熱鬧,春花似錦月幌、人聲如沸碍讯。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽捉兴。三九已至,卻和暖如春录语,著一層夾襖步出監(jiān)牢的瞬間倍啥,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評論 1 274
  • 我被黑心中介騙來泰國打工澎埠, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留虽缕,地道東北人。 一個月前我還...
    沈念sama閱讀 49,299評論 3 379
  • 正文 我出身青樓蒲稳,卻偏偏與公主長得像氮趋,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子江耀,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,870評論 2 361

推薦閱讀更多精彩內(nèi)容

  • 算法思想貪心思想雙指針排序快速選擇堆排序桶排序荷蘭國旗問題二分查找搜索BFSDFSBacktracking分治動態(tài)...
    第六象限閱讀 3,130評論 0 0
  • <center>#1 Two Sum</center> link Description:Given an arr...
    鐺鐺鐺clark閱讀 2,164評論 0 3
  • 動態(tài)規(guī)劃 111. 爬樓梯思路類似斐波那契數(shù)列注意考慮第 0 階的特殊情況 272. 爬樓梯 II思路類似上題剩胁,只...
    6默默Welsh閱讀 2,435評論 0 1
  • 我餓了。昨晚的這個時候我讓陳蕾請我吃蛋撻祥国。她問一個蛋撻多少錢昵观。她說她最近沒錢。
    花小咸閱讀 236評論 0 0
  • 要說黃小廚版《深夜食堂》最大的貢獻(xiàn)是什么? 戲醬覺得是向更多人普及了日本版《深夜食堂》壁查。 從2009年開始椒惨,《深夜...
    SoloOnceMore閱讀 818評論 0 0