2024-03-24碼農

最近，網上又一個貼文火了，是關於一個中廠總監的薪資收入。看完之後，我簡直是又羨慕又感慨。這位總監四年收入竟然高達196萬，稅後到手143萬。這數位放在哪兒都夠耀眼的，但這背後的故事，又有幾人能真正看見呢？

從62萬起步，年薪漲到200萬，這種速度和高度，真的不是常人能達到的。可見，這位總監的努力和付出肯定是超乎常人的。就像那句老話，「十年寒窗無人問，一舉成名天下知」。我們看到的是他現在的輝煌，卻沒看到他過去的艱辛。

這讓我想到了那些夢想著高薪工作的人們。大家都好奇，哪些行業能讓人薪水翻倍，過上所謂的「高品質生活」？高薪往往出現在高科技、金融、醫療、法律等領域，這些行業對專業技能的要求極高，但同時給出的報酬也相對吸引人。

比如金融行業，那可是高薪的代名詞。投資銀行、風險管理，還有那些基金經理、證券分析師，聽著就覺得不一般。

科技行業的吸金能力也是杠杠的。在這個數位化速度飛快的時代，軟體開發、數據科學、人工智慧這些領域的大佬們，薪水自然是水漲船高。

醫療行業同樣不容小覷。醫生、外科醫生、牙醫等專業人才，他們的薪資單上的數位，也足夠讓人羨慕一把。

法律行業，哦，那更是「金」職業。律師事務所、法院的大佬們，每個月的收入，絕對是你我望塵莫及的。

要真正走向高薪的職業道路，除了個人能力和努力，運氣也是很重要的。有時候，選對了行業，選對了公司，再加上一點點的機遇，可能就能讓你的職業生涯一飛沖天！

下面是今天的演算法題

# 三數之和

演算法題目

給你一個包含 n 個整數的陣列 `nums`，判斷 `nums` 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有滿足條件且不重復的三元組。

註意：答案中不可以包含重復的三元組。

引言

三數之和問題是一個經典的陣列處理問題，在演算法面試中經常出現。它不僅測試了候選人對陣列操作的熟練程度，還涉及到如何有效地處理重復值和尋找合適的演算法策略以降低時間復雜度。

演算法思路

排序：首先對陣列進行排序，這是後續去重和最佳化搜尋的基礎。
遍歷：遍歷排序後的陣列，對於每個元素，使用雙指標在其之後的部份尋找兩個數，使得這三個數的和為0。
雙指標搜尋：雙指標一前一後夾逼，尋找兩個數使得它們的和加上當前遍歷到的數等於0。
去重：在遍歷和雙指標搜尋過程中，需要跳過重復的元素，以避免重復的三元組出現。

程式碼實作

C語言實作

#include<stdio.h>#include<stdlib.h>intcompare(constvoid *a, constvoid *b){return (*(int *)a - *(int *)b);}int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){ qsort(nums, numsSize, sizeof(int), compare); *returnSize = 0;int capacity = 100; // 初始化陣列大小int** res = (int**)malloc(capacity * sizeof(int*)); *returnColumnSizes = (int*)malloc(capacity * sizeof(int));for (int i = 0; i < numsSize - 2; i++) {if (i > 0 && nums[i] == nums[i-1]) continue; // 去重int left = i + 1, right = numsSize - 1;while (left < right) {int sum = nums[i] + nums[left] + nums[right];if (sum == 0) {if (*returnSize >= capacity) { // 動態調整陣列大小 capacity *= 2; res = (int**)realloc(res, capacity * sizeof(int*)); *returnColumnSizes = (int*)realloc(*returnColumnSizes, capacity * sizeof(int)); } res[*returnSize] = (int*)malloc(3 * sizeof(int)); res[*returnSize][0] = nums[i]; res[*returnSize][1] = nums[left]; res[*returnSize][2] = nums[right]; (*returnColumnSizes)[*returnSize] = 3; (*returnSize)++;while (left < right && nums[left] == nums[left+1]) left++; // 去重while (left < right && nums[right] == nums[right-1]) right--; // 去重 left++; right--; } elseif (sum < 0) { left++; } else { right--; } } }return res;}

Java實作

import java.util.ArrayList;import java.util.Arrays;import java.util.List;public classSolution{publicList<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> res = new ArrayList<>();for (int i = 0; i < nums.length - 2; i++) {if (i > 0 && nums[i] == nums[i-1]) continue; // 去重 int left = i + 1, right = nums.length - 1;while (left < right) { int sum = nums[i] + nums[left] + nums[right];if (sum == 0) { res.add(Arrays.asList(nums[i], nums[left], nums[right]));while (left < right && nums[left] == nums[left+1]) left++; // 去重while (left < right && nums[right] == nums[right-1]) right--; // 去重left++; right--; } elseif (sum < 0) {left++; } else {right--; } } }return res; }}

Python實作

defthree_sum(nums): nums.sort() res = []for i in range(len(nums) - 2):if i > 0and nums[i] == nums[i - 1]:continue# Skip the same result l, r = i + 1, len(nums) - 1while l < r: total = nums[i] + nums[l] + nums[r]if total == 0: res.append([nums[i], nums[l], nums[r]])while l < r and nums[l] == nums[l + 1]: l += 1# Skip the same resultwhile l < r and nums[r] == nums[r - 1]: r -= 1# Skip the same result l += 1; r -= 1elif total < 0: l += 1else: r -= 1return res