几数之和的题目

总结：

两数之和——哈希表：时间复杂度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那道题不太一样，要求不一样，这个更为简单一些。

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;
    }
};

几数之和的题目

猜你在找的算法相关文章