N数之和 | Zouyu's Blog

最近新写算法，发现N数之和问题的写法又不能一次写出来了，会出现一点小问题。遂重写一遍记录于此。

两数之和

直接用暴力法会超时，这时候只能以空间换时间。
用一个哈希表将之前遍历过的元素存起来。（因为需要知道每个元素对应的索引是什么，所以不能用集合之类的结构）

遍历过程中，去哈希表中找之前的元素 + 当前元素 满足条件的结果，找到即可返回。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> mp;
        vector<int> ans;
        for(int i = 0;i<nums.size();i++){
            if(mp.count(target - nums[i])){
                ans.push_back(i);
                ans.push_back(mp[target - nums[i]]);
                break;
            }
            mp[nums[i]] = i;
        }
        return ans;
    }
};

三数之和

可以将该问题转换为两数之和。
因为是三个数，所以当第一个数固定的时候，该问题就转换为了两数之和问题。
先用一个for循环处理第一个数a。之后在a之后的元素中找出满足条件的b和c就找到了三数之和的所有解。
该问题要求返回的三元组中的内容不是索引，所以不需要特意记录索引。

题目要求返回的三元组不能重复，所以需要去重。

对a去重。考虑条件，[-1,-1,-1,0,1,2,2]。在遍历过程中，如果nums[i] == nums[i - 1]，这时候a分别取值为nums[i]和nums[i-1]去寻找b和c，找到的三元素是重复的。（b和c一样，然后a也一样，所以三元组是重复的）

对b，c去重。在寻找b、c的过程中使用了双指针。如果指针移动后指向的元素与当前元素相同，那么指针就白白移动了。举例：-1,0,0,1,1中，假设a = -1,b = 0,c = 1，指针移动后left++,right--;b还是0，c还是1。依然满足条件，但这个新是三元组是重复的。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(),nums.end());  // 需要先排序，否则无法使用双指针来找满足条件的结果。
        for(int i = 0;i<nums.size();i++){
            if(i > 0 && nums[i] == nums[i - 1]) continue;  // a去重
            int left = i + 1,right = nums.size() - 1;
            while(left < right){  // 由于b和c不能为一个数，所以left 不能等于right
                int temp = nums[i] + nums[left] + nums[right];
                if(temp > 0){
                    right--;
                    while(left < right && nums[right] == nums[right + 1]) right--; //不必要写，但这样也算剪枝了。没有这句的话，新right指针指向的数大小不变，下次循环回来right还是会减去1。
                }else if(temp < 0){
                    left++;
                    while(left < right && nums[left] == nums[left - 1]) left++; // 同上一个注释的right
                }else{
                    ans.push_back({nums[i],nums[left],nums[right]});
                    right--;
                    left++;
                    while(left < right && nums[right] == nums[right + 1]) right--;  //b、c去重
                    while(left < right && nums[left] == nums[left - 1]) left++;
                }
            }
        }
        return ans;
    }
};

四数之和

[四数之和](18. 四数之和 - 力扣（LeetCode）)

三数之和固定一个元素可以转化为两数之和，那么四数之和固定一个元素就转换为三数之和了。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ans;
        sort(nums.begin(),nums.end());  //还是先排序
        for(int k = 0;k<nums.size();k++){
            if(k > 0 && nums[k] == nums[k - 1]) continue;  //同样的去重（第一个数）
            for(int i = k + 1;i<nums.size();i++){
                // 去重（第二个数）这里为什么是i > k + 1而不是i > 0 ? 
                // 因为i只有在k + 1的时候考虑i的去重。否则i前面只有一个数nums[k]就没必要去重
                // 如果这里是i > 0，那么nums[k] = nums[i]的情况（第一个数和第二个数相等）也被去掉了
                if(i > k + 1 && nums[i] == nums[i - 1]) continue;  
                int left = i + 1,right = nums.size() - 1;
                while(left < right){
                    long long temp = (long long)nums[k] + nums[i] + nums[left] + nums[right];
                    if(temp < target){
                        left++;
                        while(left < right && nums[left] == nums[left - 1]) left++;
                    }else if(temp > target){
                        right--;
                        while(left < right && nums[right] == nums[right + 1]) right--;
                    }else{
                        ans.push_back({nums[k],nums[i],nums[left],nums[right]});
                        left++,right--;
                        while(left < right && nums[left] == nums[left - 1]) left++;
                        while(left < right && nums[right] == nums[right + 1]) right--;
                    }
                }
            }
        }
        return ans;
    }
};