思維導(dǎo)圖整理大廠面試高頻數(shù)組補(bǔ)充1: 最接近的三數(shù)之和和三數(shù)之和的兩個(gè)不同之處, 力扣16

longmon 發(fā)布于2021-11-12 10:36 / 2982人閱讀

摘要：此專欄文章是對力扣上算法題目各種方法的總結(jié)和歸納整理出最重要的思路和知識重點(diǎn)并以思維導(dǎo)圖形式呈現(xiàn)當(dāng)然也會加上我對導(dǎo)圖的詳解目的是為了更方便快捷的記憶和回憶算法重點(diǎn)不用每次都重復(fù)看題解畢竟算法不是做了一遍就能完全記住的所

此專欄文章是對力扣上算法題目各種方法的總結(jié)和歸納, 整理出最重要的思路和知識重點(diǎn)并以思維導(dǎo)圖形式呈現(xiàn), 當(dāng)然也會加上我對導(dǎo)圖的詳解.

目的是為了更方便快捷的記憶和回憶算法重點(diǎn)(不用每次都重復(fù)看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經(jīng)知道解題思路和方法, 想進(jìn)一步加強(qiáng)理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據(jù)題號先去力扣看看官方題解, 然后再看本文內(nèi)容).

關(guān)于本專欄所有題目的目錄鏈接, 刷算法題目的順序/注意點(diǎn)/技巧, 以及思維導(dǎo)圖源文件問題請點(diǎn)擊此鏈接.

想進(jìn)大廠, 刷算法是必不可少的, 歡迎和博主一起打卡刷力扣算法! 博主同步更新了算法視頻講解, 更易于理解, 不想看文章的 歡迎來看!

關(guān)注博主獲得題解更新的最新消息!!!

文章目錄

0.導(dǎo)圖整理
1.和三數(shù)之和的相同點(diǎn)
2.判斷的情況不同
3.去重的方式不同
4.最大最小值優(yōu)化
源碼
Python:
java:

題目鏈接: https://leetcode-cn.com/problems/3sum-closest/solution/si-wei-dao-tu-zheng-li-he-san-shu-zhi-he-2k6j/

0.導(dǎo)圖整理

1.和三數(shù)之和的相同點(diǎn)

原本在整理 n數(shù)之和系列時(shí)是沒有整理此題的, 后來在重看三數(shù)之和時(shí), 發(fā)現(xiàn)了這樣的評論: 百度一面題目: 找三數(shù)和最接近0, 只要將此題中的target設(shè)置0即可, 所以又重新補(bǔ)充了此題!

本題是三數(shù)之和的進(jìn)階版, 在思想上和三數(shù)之和還是很相似的: 先對數(shù)組進(jìn)行排序, 之后用雙指針進(jìn)行空間優(yōu)化, 同時(shí)注意去重操作. 本質(zhì)的思想幾乎是一樣的, 所以對本題不太理解的朋友, 可以先看完上面鏈接中的三數(shù)之和, 再來看本題題解.

但還是有一些和三數(shù)之和 不同的地方, 主要體現(xiàn)在下面的兩個(gè)方面:

2.判斷的情況不同

在三數(shù)之和中只需要判斷相等這一種情況, 其他情況不需要判斷, 操作起來是非常簡便的, 而本題中每次求和之后都需要進(jìn)行判斷(無論是相等, 還是大于或小于的情況)來找出最接近的數(shù), 這大大增加需要進(jìn)行判斷的工作量, 所以在代碼的寫法上也有很大的不同之處.

3.去重的方式不同

因?yàn)?三數(shù)之和 沒那么多的判斷情況, 所以利用了兩層for循環(huán)來遍歷, 去重的操作也比較簡單.

        for first in range(n):            # 需要和上一次枚舉的數(shù)不相同            if first > 0 and nums[first] == nums[first - 1]:                continue            ......            # 枚舉 b            for second in range(first + 1, n):                # 需要和上一次枚舉的數(shù)不相同                if second > first + 1 and nums[second] == nums[second - 1]:                    continue

而本題中判斷情況比較多, 不方便使用兩重for循環(huán)(我也嘗試了使用二重循環(huán), 但發(fā)現(xiàn)在去重時(shí)候非常復(fù)雜, 不適合使用此種方法), 所以采用了while語句來進(jìn)行雙指針的遍歷, 這樣在去重操作上會簡便很多, 并且代碼中實(shí)現(xiàn)的去重方式比官方的要簡單, 而且更方便進(jìn)行記憶!

            if s > target:                    # 如果和大于 target，移動 c 對應(yīng)的指針                    k -= 1                    # 移動到下一個(gè)不相等的元素                    while j < k and nums[k] == nums[k+1]:                        k -= 1

4.最大最小值優(yōu)化

可以計(jì)算出每次三數(shù)之和的最大最小值和目標(biāo)值進(jìn)行比較, 也可以進(jìn)行優(yōu)化, 其實(shí)這種方法早在之前講解的四數(shù)之和中就已經(jīng)提到了, 但每次都計(jì)算也增加了時(shí)間消耗, 在四數(shù)之和中還有很有優(yōu)化的必要的, 但是在三數(shù)之和中是否也適用就要看具體的情況了!

源碼

Python:

class Solution:    def threeSumClosest(self, nums: List[int], target: int) -> int:        nums.sort()        n = len(nums)        best = 10**7        # 枚舉 a        for i in range(n):            # 保證和上一次枚舉的元素不相等            if i > 0 and nums[i] == nums[i - 1]:                continue            # 使用雙指針枚舉 b 和 c            j, k = i + 1, n - 1            while j < k:                s = nums[i] + nums[j] + nums[k]                # 如果和為 target 直接返回答案                if s == target:                    return target                # 根據(jù)差值的絕對值來更新答案                if abs(s - target) < abs(best - target):                    best = s                if s > target:                    # 如果和大于 target，移動 c 對應(yīng)的指針                    k -= 1                    # 移動到下一個(gè)不相等的元素                    while j < k and nums[k] == nums[k+1]:                        k -= 1                else:                    # 如果和小于 target，移動 b 對應(yīng)的指針                    j += 1                    # 移動到下一個(gè)不相等的元素                    while j < k and nums[j] == nums[j-1]:                        j += 1        return best

java:

class Solution {    public int threeSumClosest(int[] nums, int target) {        Arrays.sort(nums);        int n = nums.length;        int best = 10000000;        // 枚舉 a        for (int i = 0; i < n; ++i) {            // 保證和上一次枚舉的元素不相等            if (i > 0 && nums[i] == nums[i - 1]) {                continue;            }            // 使用雙指針枚舉 b 和 c            int j = i + 1, k = n - 1;            while (j < k) {                int sum = nums[i] + nums[j] + nums[k];                // 如果和為 target 直接返回答案                if (sum == target) {                    return target;                }                // 根據(jù)差值的絕對值來更新答案                if (Math.abs(sum - target) < Math.abs(best - target)) {                    best = sum;                }                if (sum > target) {                    // 如果和大于 target，移動 c 對應(yīng)的指針                    --k;                    // 移動到下一個(gè)不相等的元素                    while (j < k && nums[k] == nums[k+1]) {                        --k;                    }                } else {                    // 如果和小于 target，移動 b 對應(yīng)的指針                    ++j;                    // 移動到下一個(gè)不相等的元素                    while (j < k && nums[j] == nums[j-1]) {                        ++j;                    }                }            }        }        return best;    }}