這題應該是被討論到爛的題目, 但我們這邊訓練的是一個表達的邏輯以及分析的感覺, 所以還是寫一下心得
首先, 在一堆陣列中找2個數, 加總可以得到target, 回傳這兩個數的index
最簡單的怎麼做, 就是直接挑一個數, 再從數組中剩下的數字挑另一個數
class Solution {
public:
vector<int> twoSum(vector<int> &nums, int target) {
vector<int> res;
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < nums.size(); j++) {
if (i != j) {
if (nums[i] + nums[j] == target) {
res = {i, j};
}
}
}
}
return res;
}
};這非常輕鬆, 也是一個入門磚, 這時間複雜度為O(n²), 題目要求不能在o(n)的時間完成
其實加入這個條件, 就會變得很有水準,
等於是我們只能走一遍, 並且在搜索的時候, 不能花時間在往回找條件
這邊就是熟悉的hashmap, 通過hashmap找直指需要o(1)的時間
所以我們可以將過往的記錄用{val: index}記錄下來
class Solution {
public:
vector<int> twoSum(vector<int> &nums, int target) {
std::unordered_map<int, int> map;
for(int i = 0; i < nums.size(); i++){
int goal = target - nums[i];
if(map.count(goal) == 0){
map[nums[i]] = i;
}else{
return {i, map[goal]};
}
}
return {};
}
};到這邊two sum就結束了
接著我們來看3 sum, 三數之和為0
一樣可以用上面的暴力法, 只是時間複雜度就來到O(n³), 太久了, 加上會出現重複的數組
首先我們要分幾個部分去探討,
1. 當陣列內容小於三個就一概回傳空
2. 做排序3. 若陣列第一個數字大於0, 以及最後一個數字小於0, 就跟變了心的女友一樣, 一定不會有結果, 回傳空
4. 固定住一個index(i), 然後在這個數的後方設置r, l兩個指針, r在index之後, l 在陣列之尾
5. 當i , r, l 的值相加為0, 加完答案後,移動r, l, 因為可能還有別種組合, 但切記，r, l 若移動後的值不變, 我們得移到會變為止, 因為要避免重複的值出值, 例如[-1, -1, -1, 2]
r的index從1 -> 2, 值都是-1, 這樣會再多加一次6. 若i , r, l 的值相加為<0, 移動l, 因為值太小了, 得把l加大
7. 反之i , r, l 的值相加為>0, 移動r, 因為值太大了, 得把r縮小
8. 移動i, 但要切記下個i若還是同個數, 要跳過, 重複原理分上方第五點一樣
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
if(nums.size() < 3){
return res;
}
for(int i = 0; i < nums.size();i++){
if(i != 0 && nums[i] == nums[i -1]){
continue;
}
int l = i + 1;
int r = nums.size() -1;
while(l < r){
if(nums[l] + nums[r] + nums[i] == 0){
res.push_back({nums[l], nums[r], nums[i]});
while(l < r && nums[l] == nums[l + 1]){
l++;
}
l++;
while(l < r && nums[r] == nums[r - 1]){
r--;
}
r--;
}else if(nums[l] + nums[r] + nums[i] < 0){
l++;
}else{
r--;
}
}
}
return res;
}
};
若要求不能sort, 那只能先一樣fixed住一個數, 然後開始對其他的值做two sum, 還要再多加一些條件處理
class Solution {
public:
vector<vector<int>> threeSum(vector<int> &nums) {
if (nums.size() < 3)
return {};
vector<vector<int>> res;
unordered_set<int> visited; // 用來記錄是否已經走過這個數字了
for (int i = 0; i < nums.size(); i++) {
if (visited.count(nums[i])) {
continue; //走訪過就跳掉
}
unordered_map<int, int> table{{nums[i], i}};// 紀錄table, 記得要先把i的資訊放進去
unordered_set<int> used;// 紀錄有沒有用過, 否則會一直重複 // 接著做的事跟two sum一樣, 但是條件判斷會稍稍改變
int target = -nums[i];
for (int j = i + 1; j < nums.size(); j++) {
if (visited.count(nums[j]) || used.count(nums[j])) {
continue;// 若用過, 就不要再重複一次了
}
int cur = target - nums[j];
// 若找到cur, 得先確定他是不是之前已經用過的index if (table.count(cur) && table[cur] != i && table[cur] != j) {
res.push_back({nums[i], nums[j], nums[table[cur]]}); used.insert(nums[j]);
used.insert(nums[table[cur]]);
}
table[nums[j]] = j;
}
visited.insert(nums[i]);
}return res;
}
};
4sum 基本上就跟3sum一樣, 就變先fixed 兩個數字, 記得第二個數字也要跳重複數字就是了
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
if(nums.size()< 4) return {};
sort(nums.begin(), nums.end());
vector<vector<int>> res;
for(int i = 0; i < nums.size();i++){
if(i != 0 && nums[i] == nums[i - 1])continue;
for(int j = i +1; j < nums.size(); j++){
if(j != i + 1 && nums[j] == nums[j -1]) continue;
int l = j + 1;
int r = nums.size() -1;
while(l < r){
if(nums[i] + nums[j] + nums[l] + nums[r] == target){
res.push_back({nums[i], nums[j], nums[l], nums[r]});
while(l < r && nums[l] == nums[l + 1]){
l++;
}
l++;
while(l < r && nums[r] == nums[r - 1]){
r--;
}
r--;
}else if(nums[i] + nums[j] + nums[l] + nums[r] < target){
l++;
}else{
r--;
}
}
}
}
return res;
}
};
