几数之和的题目

总结：

两数之和——哈希表：时间复杂度O(n)，暴力解法O(n^2)

三数之和——双指针：一层i的for循环，双指针left和right。时间复杂度O(n^2)，暴力解法O(n^3)

四数之后——双指针：两层i和k的for循环，双指针left和right，时间复杂度O(n^3)，暴力解法O(n^4)

再增加也是一样的，三个、四个甚至更多数之和都是这个方法，代码也是差不多，思路都一样的，有几个小地方需要注意：（1）给的数组一定要进行排序；（2）每个下标的数字都要进行去重，循环里头的去重和双指针的left和right去重，去重基本都是当前位和前一位去比较，不能当前位和下一位比较，别的倒也是没啥了，细心一点就能写对。

四数相加II那道题不太一样，要求不一样，这个更为简单一些。

@H_301_27@

class Solution {
public:
    vector<int> twoSum(vector<int>& nums,int target) {
        unordered_map <int,1)">int> map;//不需要有序，所以用这个
        for(int i = 0; i < nums.size(); i++) {
            auto iter = map.find(target - nums[i]);find函数返回的是迭代器
            if(iter != map.end()) {这句话表示找到了target-nums[i]这个元素
                return {iter->second,i};返回找到的元素的下标，还有i这个下标
                
            }
            map.insert(nums[i],i);如果没找到，不存在里头的话就添加进行
        }
        return {};
    }
};
这道题还有变体，要是说给你一个数组，让你在里头找所有两个数之和等于target的元组，那就跟三数之和四数之后一样了，双指针法解决，注意去重。

: vector<vector<int>> threeSum(vector<int>& nums) { 这道题如果使用哈希表解决的话，去重会非常的麻烦，所以最好是采用双指针解法先对数组排序，判断特殊情况，过程中要注意去重操作，特别是去重的位置，时机不对都会漏掉情况 vector<vector<int>> result;定义二维数组容器 sort(nums.begin(),nums.end()); 找出a+b+c = 0 a=nums[i],b=nums[left],c=nums[right] int i=0; i<nums.size(); i++) { 特殊情况，排序之后如果第一个元素都大于0了，那就不能存在了 if(nums[i] > 0) result; 去重,这里一定要注意，不能是i和i+1进行比较去重，否则会漏掉-1,-1,2这种情况。 if(i>0 && nums[i]==nums[i-1]) continue; int left = i+; int right = nums.size()-while(right > left) { if(nums[i]+nums[left]+nums[right] > ) right--; else if(nums[i]+nums[left]+nums[right] < ) left++else { result.push_back(vector<int>{nums[i],nums[left],nums[right]});将这个结果放到二维数组中去重逻辑 while(right>left && nums[right]==nums[right-]) right--; while(right>left && nums[left]==nums[left+]) left++; 找到答案，双指针同时收缩，因为是排序的数组 right--; left++; } } } result; } };

int>> fourSum(vector< target) { vector<vector<int>> result; sort(nums.begin(),1)">int k=0; k<nums.size(); k++肯定要对k这这个最前面的元素进行去重，但不能是i和i+1,否则会漏掉情况 if(k>0 && nums[k]==nums[k-int i=k+1; i<nums.size(); i++) { 对i也要进行去重，同上 if(i>k+1 && nums[i]==nums[i-]) while(right>left) { if(nums[k]+nums[i]+nums[left]+nums[right] > target) right--if(nums[k]+nums[i]+nums[left]+nums[right] < target) left++ { result.push_back(vector<int>{nums[k],nums[i],nums[right]}); 去重逻辑 ]) right--; ]) left++找到了一组值，left和right同步缩进 right--; left++; } } } } result; } };

: int fourSumCount(vector<int>& A,vector<int>& B,1)">int>& C,1)"> D) { 本题的思路可以是：利用哈希表，先统计a+b的值，把值作为map的key，出现的次数作为value，然后遍历c和d，如果在map中找到了0-（c+d）的值，就把个数+1，直到最后 unordered_map< umap; a : A) { b : B) { umap[a+b]++; } } int count = ; c : C) { d : D) { if(umap.find(0-(c+d)) != umap.end()) count += umap[0-(c+d)]; } } count; } };

几数之和的题目

猜你在找的算法相关文章