18. 4Sum

Description

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

Solution

Four-pointers, O(n^3) time

先對數(shù)組進(jìn)行排序衷敌,注意去重祟绊。跟3Sum的思路一樣裁良。

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> quadruplets = new ArrayList();
        if (nums == null || nums.length < 4) return quadruplets;
        
        Arrays.sort(nums);
        int i = 0;
        int n = nums.length;
        
        while (i < n - 3) {
            int j = i + 1;
            while (j < n - 2) {
                int k = j + 1;
                int l = n - 1;
                while (k < l) {
                    int sum = nums[i] + nums[j] + nums[k] + nums[l];
                    if (sum < target) {
                        ++k;
                    } else if (sum > target) {
                        --l;
                    } else {
                        quadruplets.add(
                            Arrays.asList(nums[i], nums[j], nums[k], nums[l]));
                        while (++k < l && nums[k] == nums[k - 1]) {};
                        while (k < --l && nums[l] == nums[l + 1]) {};
                    }
                }
                while (++j < n - 2 && nums[j] == nums[j - 1]) {};
            }
            while (++i < n - 3 && nums[i] == nums[i - 1]) {};
        }
        
        return quadruplets;
    }
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市厕九,隨后出現(xiàn)的幾起案子忧换,更是在濱河造成了極大的恐慌盔憨,老刑警劉巖洗搂,帶你破解...
    沈念sama閱讀 222,590評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異沛申,居然都是意外死亡劣领,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,157評論 3 399
  • 文/潘曉璐 我一進(jìn)店門铁材,熙熙樓的掌柜王于貴愁眉苦臉地迎上來尖淘,“玉大人,你說我怎么就攤上這事著觉〈迳” “怎么了?”我有些...
    開封第一講書人閱讀 169,301評論 0 362
  • 文/不壞的土叔 我叫張陵饼丘,是天一觀的道長趁桃。 經(jīng)常有香客問我,道長肄鸽,這世上最難降的妖魔是什么卫病? 我笑而不...
    開封第一講書人閱讀 60,078評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮典徘,結(jié)果婚禮上蟀苛,老公的妹妹穿的比我還像新娘。我一直安慰自己逮诲,他們只是感情好帜平,可當(dāng)我...
    茶點故事閱讀 69,082評論 6 398
  • 文/花漫 我一把揭開白布幽告。 她就那樣靜靜地躺著,像睡著了一般罕模。 火紅的嫁衣襯著肌膚如雪评腺。 梳的紋絲不亂的頭發(fā)上帘瞭,一...
    開封第一講書人閱讀 52,682評論 1 312
  • 那天淑掌,我揣著相機(jī)與錄音,去河邊找鬼蝶念。 笑死抛腕,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的媒殉。 我是一名探鬼主播担敌,決...
    沈念sama閱讀 41,155評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼廷蓉!你這毒婦竟也來了全封?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,098評論 0 277
  • 序言:老撾萬榮一對情侶失蹤桃犬,失蹤者是張志新(化名)和其女友劉穎刹悴,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體攒暇,經(jīng)...
    沈念sama閱讀 46,638評論 1 319
  • 正文 獨居荒郊野嶺守林人離奇死亡土匀,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,701評論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了形用。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片就轧。...
    茶點故事閱讀 40,852評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖田度,靈堂內(nèi)的尸體忽然破棺而出妒御,到底是詐尸還是另有隱情,我是刑警寧澤镇饺,帶...
    沈念sama閱讀 36,520評論 5 351
  • 正文 年R本政府宣布乎莉,位于F島的核電站,受9級特大地震影響兰怠,放射性物質(zhì)發(fā)生泄漏梦鉴。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,181評論 3 335
  • 文/蒙蒙 一揭保、第九天 我趴在偏房一處隱蔽的房頂上張望肥橙。 院中可真熱鬧,春花似錦秸侣、人聲如沸存筏。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,674評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽椭坚。三九已至予跌,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間善茎,已是汗流浹背券册。 一陣腳步聲響...
    開封第一講書人閱讀 33,788評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點兒被人妖公主榨干…… 1. 我叫王不留垂涯,地道東北人烁焙。 一個月前我還...
    沈念sama閱讀 49,279評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像耕赘,于是被迫代替她去往敵國和親骄蝇。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,851評論 2 361

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

  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問題, 分享了一些自己做題目的經(jīng)驗操骡。 張土汪:刷leetcod...
    土汪閱讀 12,748評論 0 33
  • 1九火、什么是進(jìn)程? 進(jìn)程可以簡單的理解為執(zhí)行中的程序册招,程序是我們放在硬盤中的一段代碼岔激,而通過創(chuàng)建進(jìn)程,系統(tǒng)將程序放入...
    IvanHung閱讀 318評論 0 2
  • 目錄 編譯 SDK 報錯記錄 打包固件 編譯 SDK 報錯記錄 參考網(wǎng)站SDK:FireFly-Rk3288 5....
    KevinChiu閱讀 2,475評論 1 0
  • 宮殿般的房子跨细,華麗的水晶吊燈灑下一地璀璨的光鹦倚。 來來往往衣著好貴的人物,盡酒賣笑冀惭,燈紅酒綠震叙。 幔紗般的紫色長裙,裙...
    一心小記閱讀 400評論 0 3
  • 今天來辦房產(chǎn)證了划址,很早就來了,到這里五點半限府,我起那么早的原因是我每天都會早起夺颤,結(jié)果到這里已經(jīng)有兩個人站在門口了,由...
    一星若月閱讀 190評論 0 0