寫在前面:
程序員分兩種辞州，會(huì)算法的程序員和不會(huì)算法的程序員。幾乎沒有一個(gè)一線互聯(lián)網(wǎng)公司招聘任何類別的技術(shù)人員是不考算法的件蚕，程序猿們都懂的孙技，現(xiàn)在最權(quán)威流行的刷題平臺(tái)就是 LeetCode产禾。
Question: 3Sum
Difficulty:Medium Tag:Array
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
Solution:
以下代碼皆是本人用 C++寫的，覺得還不錯(cuò)的話別忘了點(diǎn)個(gè)贊哦牵啦。各位同學(xué)們?nèi)绻衅渌咝Ы忸}思路還請(qǐng)不吝賜教亚情，多多學(xué)習(xí)。
A1哈雏、暴力解法
粗暴進(jìn)行循環(huán)遍歷楞件，問題復(fù)雜化，不可取
Time complexity : O(n^2) 354ms裳瘪，代碼如下
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> temp;
std::sort(nums.begin(), nums.end());
map<int,int> map;
for (int i=0; i<nums.size(); i++) {
map[nums[i]] = i;
}
int index = INT32_MIN;
for (int i=0; i<nums.size(); i++) {
if (nums[i]>0) {
break;
}
if (index == nums[i]) {
continue;
} else{
index = nums[i];
}
int sum = -nums[i];
int index1 = INT32_MIN;
for (int j=i+1; j<nums.size(); j++) {
if (index1 == nums[j]) {
continue;
} else{
index1 = nums[j];
}
int search = sum - nums[j];
if (map.find(search) != map.end() && map[search] > i && map[search] > j) {
vector<int> vec = {nums[i],nums[j],search};
temp.push_back(vec);
}
}
}
return temp;
}
};
A2土浸、雙指針解法
減少了 map 創(chuàng)建，減少了部分一定不成立情況的計(jì)算彭羹，同
LeetCode刷算法題 - 11. Container With Most Water(盛最多水的容器)
算法時(shí)間復(fù)雜度 O(n^2)黄伊，Runtime: 110 ms，代碼如下
int x=[](){
std::ios::sync_with_stdio(false); //關(guān)閉STDIN和CIN同步 減少CIN讀入的時(shí)間派殷，可以減少50%以上还最。
cin.tie(NULL);
return 0;
}();
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
std::sort(nums.begin(), nums.end());
int left = 0, right = (int)nums.size()-1,sum = 0;
for (int i=0; i<nums.size(); i++) {
if (nums[i]>0) break;
if (i>0 && nums[i]==nums[i-1]) continue;
sum = -nums[i];
left = i+1;
right = (int)nums.size()-1;
while (left<right) {
if (nums[left]+nums[right]==sum) {
vector<int> vec = {nums[i],nums[left],nums[right]};
res.push_back(vec);
left++;right--;
while (nums[left]==nums[left-1]) left++;
while (nums[right]==nums[right+1]) right--;
} else if (nums[left]+nums[right]>sum){
right--;
} else if (nums[left]+nums[right]<sum){
left++;
}
}
}
return res;
}
};
