前往
大廳
主題

LeetCode - 16. 3Sum Closest 解題心得

Not In My Back Yard | 2021-12-17 00:00:05 | 巴幣 0 | 人氣 188

題目連結:


題目意譯:
給定一個有著 n 個整數的陣列 nums 以及一個整數 target,找到 nums 中的三個整數使得其總和最接近 target。回傳這三個整數之和。你可以假設每筆輸入恰好有著一組解。

限制:
3 ≦ nums.length ≦ 10 ^ 3
-10 ^ 3 ≦ nums[i] ≦ 10 ^ 3
-10 ^ 4 ≦ target ≦ 10 ^ 4



範例測資:
範例 1:
輸入: nums = [-1,2,1,-4], target = 1
輸出: 2
解釋: 最接近 target 的總和值為 2。(-1 + 2 + 1 = 2)


解題思維:
(nums 的索引值從 0 開始數)
一開始我們先將 nums 中的數字由小排到大。

接著我們窮舉 i 值,其中 i = 0 ~ n - 1。對於每個 nums[i] 再窮舉 (j, k) 數對(一開始 j = i + 1 、 k = n - 1 且我們將始終維持 j < k 之關係)。

當 X = nums[i] + nums[j] + nums[k] < target 時,代表著 (i, j + 1, k) 得出的數字總和有可能會更接近 target(因為已排序了,nums[j] ≦ nums[j + 1]);當 X > target 時,(i, j, k - 1) 可能更接近;當 X = target 時,(i, j + 1, k) 或 (i, j, k - 1) 都是有可能會更近的,隨便挑一個即可(因為不管誰先誰後最後都會被判斷到)。

而當中最接近 target 的 X 之值即為所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作