Re: [閒聊] 每日LeetCode
16. 3Sum Closest
給定一個長度大於3的整數陣列和一個數字target，求出最接近target的任意三數之和，
假定測資只存在恰好一解。
Example 1:
Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
法一 暴力法
思路：
1.老子直接在你面前跑三層loop
Java Code：
class Solution {
public int threeSumClosest(int[] nums, int target) {
int closest = Integer.MAX_VALUE;
int res = 0;
for(int i = 0;i < nums.length;i++)
for(int j = i + 1; j < nums.length; j++)
for(int k = j + 1; k < nums.length; k++) {
int sum = nums[i] + nums[j] + nums[k];
int diff = Math.abs(target - sum);
if(diff < closest) {
res = sum;
closest = diff;
}
}
return res;
}
}
時間複雜度O(n^3) 安心信賴TLE
法二 雙指標
思路：
1.題目要求與target最接近的sum，所以：
A + B + C = sum ==> 趨近於target
我們可以把他移項：
B + C = 趨近於target - A
該問題就會退化為在陣列裡搜尋最接近 target 的 B + C
2.先把整個陣列排序，這樣可以快速的取值且排除掉使用過的組合。
3.遍歷陣列，把nums[i]當作第一個加數A，並從右取最大和最小值當B和C。
sum = A + B + C
4.依據狀況移動指標，分兩case：
若sum > target 表示我們要再拿更小 right--
若sum < target 表示我們要拿更大 left++
這樣每一步都可以產生更小絕對值的解，不用雙層迴圈求所有和。
5.若當前的sum與target的絕對值小於diff則更新diff和res
6.返回res
Java Code：
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int res = nums[0] + nums[1] + nums[2];
int diff = Math.abs(res - target);
for (int i = 0; i < nums.length - 2; ++i) {
int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
int newDiff = Math.abs(sum - target);
if (diff > newDiff) {
diff = newDiff;
res = sum;
}
if (sum < target) ++left;
else --right;
}
}
return res;
}
}
時間複雜度：O(n^2)
告辭
--
https://i.imgur.com/fHpKflu.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.159.111.108 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1665203869.A.14A.html
推
10/08 12:42,
1年前
, 1F
10/08 12:42, 1F
推
10/08 12:49,
1年前
, 2F
10/08 12:49, 2F
推
10/08 13:01,
1年前
, 3F
10/08 13:01, 3F
討論串 (同標題文章)