1.两数之和

题目描述：


给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。


链接

思路：同一个元素不能同时使用，直接两遍for循环即可。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int sz = nums.size();
        vector<int> v;
        if(sz < 2)//元素个数小于2，不做判断
            return v;
        for(int i = 0;i < sz;++i)
        {
            for(int j = i + 1;j < sz;++j)
            {
                if(nums[i] + nums[j] == target)//等于目标值
                {
                    v.push_back(i);
                    v.push_back(j);
                    return v;
                }
            }
        }
        return v;
    }
};

2.三数之和

题目描述：


给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

链接

思路：排序+双指针法，关键点在于，如何去重。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int sz = nums.size();
        vector<vector<int>> vv;
        vector<int> v;
        if(sz < 3)//判断条件，不满足无法进行判断
            return vv;
        sort(nums.begin(),nums.end());//排序
        int first = 0;
        while(first < sz - 1 && nums[first] <= 0)
        {
            int second = first + 1;//双指针，头
            int third = sz - 1;//双指针，末尾
            while(second < third)
            {
                int sum = nums[first] + nums[second] + nums[third];//求和
                if(sum > 0)//比0大
                    --third;
                else if(sum < 0)//比0小
                    ++second;
                else
                {
                    v.push_back(nums[first]);//放入元素
                    v.push_back(nums[second]);
                    v.push_back(nums[third]);
                    vv.push_back(v);
                    v.clear();//一定要情况
                    while(second < third && nums[second] == nums[++second]);//双指针去重
                    while(second < third && nums[third] == nums[--third]);//双指针去重
                }
            }
            while(first < sz - 1 && nums[first] == nums[++first]);//固定位置去重
        }
        return vv;
    }
};

3.四数之和

题目描述：


给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：答案中不可以包含重复的四元组。

链接

思路：和求三数之和一样，固定位置，然后双指针，但是这里需要固定两个位置。仍需要去重。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int sz = nums.size();
        vector<vector<int>> vv;
        vector<int> v;
        sort(nums.begin(),nums.end());
        if(sz < 4)
            return vv;
        int first = 0;
        while(first < (sz - 3))//第一个固定位置
        {
            int second = first + 1;
            while(second < (sz - 2) )//第二个固定位置
            {
                int third = second + 1;//双指针
                int end = sz - 1;
                while(third < end)//循环判断
                {
                    int sum = nums[end] + nums[third] + nums[second] + nums[first];//求和
                    if(sum > target)
                        --end;
                    else if(sum < target)
                        ++third;
                    else
                    {
                        v.push_back(nums[first]);
                        v.push_back(nums[second]);
                        v.push_back(nums[third]);
                        v.push_back(nums[end]);
                        vv.push_back(v);
                        v.clear();
                        while(third < end && nums[third] == nums[++third]);//去重
                        while(third < end && nums[end] == nums[--end]);//去重
                    }
                }
                while(second < (sz - 2) && nums[second] == nums[++second]);//去重
            }
            while(first < (sz - 3) && nums[first] == nums[++first]);//去重
        }
        return vv;
    }
};