您好,登錄后才能下訂單哦!
這篇文章給大家分享的是有關(guān)如何解決leetcode中三數(shù)之和的問題的內(nèi)容。小編覺得挺實(shí)用的,因此分享給大家做個(gè)參考,一起跟隨小編過來看看吧。
https://leetcode-cn.com/problems/3sum-closest/
給定一個(gè)包括 n
個(gè)整數(shù)的數(shù)組 nums
和 一個(gè)目標(biāo)值 target
。找出 nums
中的三個(gè)整數(shù),使得它們的和與 target
最接近。返回這三個(gè)數(shù)的和。假定每組輸入只存在唯一答案。
例如,給定數(shù)組 nums = [-1,2,1,-4], 和 target = 1.
與 target 最接近的三個(gè)數(shù)的和為 2. (-1 + 2 + 1 = 2).
標(biāo)簽:排序和雙指針
本題目因?yàn)橐?jì)算三個(gè)數(shù),如果靠暴力枚舉的話時(shí)間復(fù)雜度會(huì)到O(n^3),需要降低時(shí)間復(fù)雜度
首先進(jìn)行數(shù)組排序,時(shí)間復(fù)雜度O(nlogn)
在數(shù)組nums中,進(jìn)行遍歷,每遍歷一個(gè)值利用其下標(biāo)i,形成一個(gè)固定值nums[i]
再使用前指針指向start = i + 1
處,后指針指向end = nums.length - 1
處,也就是結(jié)尾處
根據(jù) sum = nums[i] + nums[start] + nums[end]
的結(jié)果,判斷sum與目標(biāo)target的距離,如果更近則更新結(jié)果ans
同時(shí)判斷sum與target的大小關(guān)系,因?yàn)閿?shù)組有序,如果sum > target
則 end--
,如果sum < target
則 start++
,如果sum == target
則說明距離為0直接返回結(jié)果
整個(gè)遍歷過程,固定值為n次,雙指針為n次,時(shí)間復(fù)雜度為O(n^2)
總時(shí)間復(fù)雜度:O(nlogn) + O(n^2) = O(n^2)
class Solution { public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int ans = nums[0] + nums[1] + nums[2]; for(int i=0;i<nums.length;i++) { int start = i+1, end = nums.length - 1; while(start < end) { int sum = nums[start] + nums[end] + nums[i]; if(Math.abs(target - sum) < Math.abs(target - ans)) ans = sum; if(sum > target) end--; else if(sum < target) start++; else return ans; } } return ans; }}
感謝各位的閱讀!關(guān)于“如何解決leetcode中三數(shù)之和的問題”這篇文章就分享到這里了,希望以上內(nèi)容可以對(duì)大家有一定的幫助,讓大家可以學(xué)到更多知識(shí),如果覺得文章不錯(cuò),可以把它分享出去讓更多的人看到吧!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。