16.最接近的三數(shù)之和

16. 最接近的三數(shù)之和(雙指針)

做LeetCode16題有感材部,雙指針,即有兩個指針唯竹,一般指向一前一后乐导,如果有三個變量則固定一個,另外兩個變量使用雙指針浸颓。

舉例物臂,a+b+c=target。a产上、b棵磷、c是三個指針,我們可以固定a晋涣,移動指針b和c仪媒。

轉(zhuǎn)換成b+c=target-a。這樣就把a固定下來了

說完了雙指針的基本原理谢鹊,來做一道題算吩,即LC的第16題

首先將數(shù)組排序留凭,然后枚舉指針b和c,對特殊情況進行判斷偎巢,下面是代碼

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int l = nums.length;
        int res = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < l - 2; i++) {
            //防止重復
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int j = i + 1, k = l - 1;
            while (j < k) {
                //當前的和
                int sum = nums[i] + nums[j] + nums[k];
                //如果sum==target直接返回
                if (target == sum) return target;
                //根據(jù)絕對值差值的大小來調(diào)整指針的位置
                if (Math.abs(sum - target) < Math.abs(res - target)) {
                    res = sum;
                }
                if (sum > target) k--;
                else j++;
            }
        }
        return res;
    }
}

其他細節(jié):如果指針移動過程中有重復項蔼夜,那么可以連續(xù)移動b和c指針

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int l = nums.length;
        int res = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < l - 2; i++) {
            //防止重復
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int j = i + 1, k = l - 1;
            while (j < k) {
                //當前的和
                int sum = nums[i] + nums[j] + nums[k];
                //如果sum==target直接返回
                if (target == sum) return target;
                //根據(jù)絕對值差值的大小來調(diào)整指針的位置
                if (Math.abs(sum - target) < Math.abs(res - target)) {
                    res = sum;
                }
                if (sum > target) {
                    k--;
                    while (j<k && nums[k] == nums[k + 1])
                        k--;
                } else {
                    j++;
                    while (j<k&&nums[j]==nums[j-1]){
                        j++;
                    }
                }
            }
        }
        return res;
    }
}
?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市压昼,隨后出現(xiàn)的幾起案子求冷,更是在濱河造成了極大的恐慌,老刑警劉巖巢音,帶你破解...
    沈念sama閱讀 211,639評論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異尽超,居然都是意外死亡官撼,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,277評論 3 385
  • 文/潘曉璐 我一進店門似谁,熙熙樓的掌柜王于貴愁眉苦臉地迎上來傲绣,“玉大人,你說我怎么就攤上這事巩踏⊥核校” “怎么了?”我有些...
    開封第一講書人閱讀 157,221評論 0 348
  • 文/不壞的土叔 我叫張陵塞琼,是天一觀的道長菠净。 經(jīng)常有香客問我彪杉,道長派近,這世上最難降的妖魔是什么渴丸? 我笑而不...
    開封第一講書人閱讀 56,474評論 1 283
  • 正文 為了忘掉前任戒幔,我火速辦了婚禮溪食,結(jié)果婚禮上错沃,老公的妹妹穿的比我還像新娘枢析。我一直安慰自己,他們只是感情好,可當我...
    茶點故事閱讀 65,570評論 6 386
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著租谈,像睡著了一般。 火紅的嫁衣襯著肌膚如雪呻逆。 梳的紋絲不亂的頭發(fā)上咖城,一...
    開封第一講書人閱讀 49,816評論 1 290
  • 那天控妻,我揣著相機與錄音弓候,去河邊找鬼菇存。 笑死依鸥,一個胖子當著我的面吹牛,可吹牛的內(nèi)容都是我干的絮供。 我是一名探鬼主播壤靶,決...
    沈念sama閱讀 38,957評論 3 408
  • 文/蒼蘭香墨 我猛地睜開眼恬惯,長吁一口氣:“原來是場噩夢啊……” “哼酪耳!你這毒婦竟也來了葡兑?” 一聲冷哼從身側(cè)響起奖蔓,我...
    開封第一講書人閱讀 37,718評論 0 266
  • 序言:老撾萬榮一對情侶失蹤赞草,失蹤者是張志新(化名)和其女友劉穎讹堤,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體厨疙,經(jīng)...
    沈念sama閱讀 44,176評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡洲守,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,511評論 2 327
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了沾凄。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片梗醇。...
    茶點故事閱讀 38,646評論 1 340
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖撒蟀,靈堂內(nèi)的尸體忽然破棺而出叙谨,到底是詐尸還是另有隱情,我是刑警寧澤保屯,帶...
    沈念sama閱讀 34,322評論 4 330
  • 正文 年R本政府宣布手负,位于F島的核電站,受9級特大地震影響姑尺,放射性物質(zhì)發(fā)生泄漏竟终。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 39,934評論 3 313
  • 文/蒙蒙 一切蟋、第九天 我趴在偏房一處隱蔽的房頂上張望统捶。 院中可真熱鬧,春花似錦、人聲如沸喘鸟。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,755評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽迷守。三九已至犬绒,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間兑凿,已是汗流浹背凯力。 一陣腳步聲響...
    開封第一講書人閱讀 31,987評論 1 266
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留礼华,地道東北人咐鹤。 一個月前我還...
    沈念sama閱讀 46,358評論 2 360
  • 正文 我出身青樓,卻偏偏與公主長得像圣絮,于是被迫代替她去往敵國和親祈惶。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 43,514評論 2 348