两数之和 三数之和 四数之和

LeetCode 1.两数之和

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        unordered_map umap;//value weizhi
        //unordered_map是一种key value的存储结构
        //可以用key保存数值，用value在保存数值所在的下标。
        for(int i=0;i
            umap[nums[i]]=i;//初始化
        }

        for(int i=0;i
            auto it=umap.find(target-nums[i]);
            if(it!=umap.end()&&it->second!=i)
            {
                return {i,it->second};
            } 
        }
        return {};
    }
};

哈希表存储。

LeetCode 15.三数之和

class Solution {
public:
    vector> threeSum(vector& nums) {
        vector> result;
        sort(nums.begin(),nums.end());
        for(int i=0;i
            if(nums[i]>0) break;
            if(i>0&&nums[i]==nums[i-1]) continue;//三元组元素a去重
            
            //双指针 
            int low=i+1,high=nums.size()-1;
            while(low
                if(nums[low]+nums[high]+nums[i]>0)
                {
                    high--;
                    while(low
                    low++;
                    while(low
                    result.push_back({nums[low],nums[high],nums[i]});
                    // 去重逻辑应该放在找到一个三元组之后
                    while(low 
去重的原理都是没有比较过的元素与相邻的元素之间进行的比较。
 
去重1说明： 
去重1中，定义high的位置为pos1，首先进行的是high–，此时high的值为pos2=pos1-1。
 
因为pos1之前没有进行过比较，因此需要将其与相邻的元素进行比较，即pos2=pos1-1，所以应该比较nums[pos1]和nums[pos1-1]。
 
由于此时的high=pos1-1，因此，需要比较nums[high]==nums[high+1]。
 
if(nums[low]+nums[high]+nums[i]>0)
{
   high--;
   while(low 
去重2同去重1理。
 
去重3说明： 
去重3中，定义high的位置为pos1，因为pos1之前没有进行过比较，因此需要将其与相邻的元素进行比较，即pos2=pos1-1，所以应该比较nums[pos1]和nums[pos1-1]。由于此时的high=pos1，因此，需要比较nums[high]==nums[high-1]。
 
while(low 
去重4同去重3理。
 
2. 哈希解法 
class Solution {
public:
    vector> threeSum(vector& nums) {
        vector> result;
        sort(nums.begin(),nums.end());//-4 -1 -1 0 1 2
        for(int i=0;i
            if(nums[i]>0) break;
            if(i>0&&nums[i]==nums[i-1]) continue;//三元组元素a去重
            
            unordered_set set;
            for(int j=i+1;j
                if(j>i+2&&nums[j]==nums[j-1]&&nums[j-1]==nums[j-2]) continue;// 三元组元素b去重

                int tmp=0-(nums[i]+nums[j]);
                if(set.find(tmp)!=set.end())
                {
                    result.push_back({nums[i],nums[j],tmp});
                    set.erase(tmp);// 三元组元素c去重
                }
                else
                {
                    set.insert(nums[j]);
                }
            }
        }
        return result;
    }
};
 
哈希解法中需要注意的是去重。
 
对于a的去重用if语句:
 
if(i>0&&nums[i]==nums[i-1]) continue;//三元组元素a去重
 
对于b的去重，则需要进行如下的判断：
 
if(j>i+2&&nums[j]==nums[j-1]&&nums[j-1]==nums[j-2]) continue;// 三元组元素b去重
 
对于c的去重，需要如下的操作：
 
set.erase(tmp);// 三元组元素c去重
 
结论：方法1（双指针法）更加适合三数之和，判断去重更加的方便。
 
三、LeetCode 18 四数之和 
LeetCode 18.四数之和
 
基本框架同三数之和的双指针法。
 
class Solution {
public:
    vector> fourSum(vector& nums, int target) {
        vector> result;
        sort(nums.begin(),nums.end());

        for(int i=0;i
            if(i>0&&nums[i]==nums[i-1]) continue;
            for(int j=i+1;j
                if(j>i+1&&nums[j]==nums[j-1]) continue;

                int low=j+1;
                int high=nums.size()-1;

                while(low
                    if(nums[i]+nums[j]>target-(nums[low]+nums[high]))
                    {
                        high--;
                        while(low
                        low++;
                        while(low
                        result.push_back({nums[i],nums[j],nums[low],nums[high]});
                        while(low 
需要注意的是需要写成
 
if(nums[i]+nums[j]>target-(nums[low]+nums[high]))
 
而不是
 
if(nums[i]+nums[j]+nums[low]+nums[high]>target)
 
会报错，如下：
 
执行出错信息：
Line 19: Char 39: runtime error: signed integer overflow: 2000000000 + 1000000000 cannot be represented in type 'int' (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:28:39
最后执行的输入：
[1000000000,1000000000,1000000000,1000000000]
0