1饰迹、兩數(shù)之和 雙指針 雙for循環(huán) 哈希

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int>mp;
        for(int i =0;i<nums.size();i++){
            auto it = mp.find(target-nums[i]);
            if(it !=mp.end()){
                return {it->second,i};
            }
            mp[nums[i]]=i;
        }
        return {};
    }
};

vector<int> twoSum(vector<int>& nums, int target) {
// 先對數(shù)組排序
sort(nums.begin(), nums.end());
// 左右指針
int lo = 0, hi = nums.size() - 1;
while (lo < hi) {
int sum = nums[lo] + nums[hi];
// 根據(jù) sum 和 target 的比較愈案，移動左右指針
if (sum < target) {
lo++;
} else if (sum > target) {
hi--;
} else if (sum == target) {
return {nums[lo], nums[hi]};
}
}
return {};
}

三數(shù)字之和

class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
vector<int>vec;
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size();i++){
if (nums[i] > 0) {
return res;
}

        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        int left =i+1;
        int right = nums.size()-1;
        while(left < right){
            if(nums[i] +nums[left] + nums[right] < 0){
                left++;      
            } else if (nums[i] +nums[left] + nums[right] > 0) {
                right--;
            } else{
               res.push_back(vector<int>{nums[i], nums[left], nums[right]}); 
               //去重
                while (right > left && nums[right] == nums[right - 1]) right--;
                while (right > left && nums[left] == nums[left + 1]) left++;

                // 找到答案時候齿，雙指針同時收縮
                right--;
                left++;
            }
        }
    }
    return res;
}

};

四數(shù)之和

using LL = long long;

class Solution {
public:
// 思路：類比《三數(shù)之和》，先排序，然后枚舉并固定a b，利用首尾指針尋找 c d
vector<vector<int>> fourSum(vector<int>& nums, int x) {
if(nums.size()<4)return {};
vector<vector<int>> res;
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size()-3;++i){
// 由于nums[i]對應的元素值已經(jīng)枚舉過了，不需要再次枚舉了
if(i>0&&nums[i]==nums[i-1])continue;
// 以下代碼與 三數(shù)之和 一樣
for(int j=i+1;j<nums.size()-2;++j){
// 由于nums[i]對應的元素值已經(jīng)枚舉過了痛单，不需要再次枚舉了
if(j>i+1&&nums[j]==nums[j-1])continue;
// 首尾指針來尋找c d
int l=j+1,r=nums.size()-1;
while(l<r){
LL sum=0LL+nums[i]+nums[j]+nums[r]+nums[l];
if(sum>x)r--;// sum太大，向左逼近
else if(sum<x)l++;// sum太小劲腿，向右逼近
else{
// 添加結(jié)果
res.push_back({nums[i],nums[j],nums[l],nums[r]});
// 縮小區(qū)間
l++,r--;
while(l<r&&nums[l]==nums[l-1])l++;
while(l<r&&nums[r]==nums[r+1])r--;
}
}
}
}
return res;
}
};

n數(shù)之和
/* 注意：調(diào)用這個函數(shù)之前一定要先給 nums 排序 */
vector<vector<int>> nSumTarget(
    vector<int>& nums, int n, int start, int target) {

    int sz = nums.size();
    vector<vector<int>> res;
    // 至少是 2Sum旭绒，且數(shù)組大小不應該小于 n
    if (n < 2 || sz < n) return res;
    // 2Sum 是 base case
    if (n == 2) {
        // 雙指針那一套操作
        int lo = start, hi = sz - 1;
        while (lo < hi) {
            int sum = nums[lo] + nums[hi];
            int left = nums[lo], right = nums[hi];
            if (sum < target) {
                while (lo < hi && nums[lo] == left) lo++;
            } else if (sum > target) {
                while (lo < hi && nums[hi] == right) hi--;
            } else {
                res.push_back({left, right});
                while (lo < hi && nums[lo] == left) lo++;
                while (lo < hi && nums[hi] == right) hi--;
            }
        }
    } else {
        // n > 2 時，遞歸計算 (n-1)Sum 的結(jié)果
        for (int i = start; i < sz; i++) {
            vector<vector<int>> 
                sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
            for (vector<int>& arr : sub) {
                // (n-1)Sum 加上 nums[i] 就是 nSum
                arr.push_back(nums[i]);
                res.push_back(arr);
            }
            while (i < sz - 1 && nums[i] == nums[i + 1]) i++;
        }
    }
    return res;
}