【优选算法题练习】day3

摘星

发布于 2023-10-15 15:53:06

1530

发布于 2023-10-15 15:53:06

一、15. 三数之和

1.题目简介

15. 三数之和给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。

2.解题思路

3.代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        //1.排序
        sort(nums.begin(), nums.end(), [](int& x, int& y){return x < y;});
        //2.先确定三个数中最小的那个数a，然后用双指针法去查找另外两个数b和c，使b + c = -a;
        for(int i = 0;i < nums.size() - 2; ++i)
        {

            if(i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = nums.size() - 1;
            while(left < right)
            {
                int sum = nums[left] + nums[right];
                if(sum < -nums[i])
                {
                    left++;
                    while(left < right && nums[left] == nums[left - 1]) left++;//用while是因为可能有很多重复的数字，要去重
                }
                else if(sum > -nums[i])
                {
                    right--;
                    while(left < right && nums[right] == nums[right + 1]) right--;
                }
                else
                {

                    ret.push_back({nums[i], nums[left], nums[right]});
                    left++;
                    while(left < right && nums[left] == nums[left - 1]) left++;
                    right--;
                    while(left < right && nums[right] == nums[right + 1]) right--;
                }
            }
        }
        return ret;
    }
};

4.运行结果

二、18. 四数之和

1.题目简介

18. 四数之和给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）： 0 <= a, b, c, d < n（a、b、c 和 d 互不相同） nums[a] + nums[b] + nums[c] + nums[d] == target 你可以按任意顺序返回答案。

2.解题思路

3.代码

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ret;
        //1.排序
        sort(nums.begin(), nums.end(), [](int& x, int& y){return x < y;});
        //2.两层for循环分别确定两个元素(一个最大一个最小)，再用指针法确定剩下的两个元素
        for(int i = 0;i < nums.size(); ++i)
        {
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            for(int j = nums.size() - 1;j >= 0; --j)
            {
                if(j <nums.size() - 1 && nums[j] == nums[j + 1]) continue;
                long long sum1 = nums[i] + nums[j];
                int left = i + 1, right = j - 1;
                while(left < right)
                {
                    long long sum2 = nums[left] + nums[right];
                    if(sum2 < (target-sum1))
                    {
                        left++;
                        while(left < right && nums[left] == nums[left - 1]) left++;
                    }
                    else if(sum2 > (target-sum1))
                    {
                        right--;
                        while(left < right && nums[right] == nums[right + 1]) right--;
                    }
                    else
                    {
                        ret.push_back({nums[i], nums[j], nums[left], nums[right]});
                        left++;
                        while(left < right && nums[left] == nums[left - 1]) left++;
                        right--;
                        while(left < right && nums[right] == nums[right + 1]) right--;
                    }
                }
            }
        }
        return ret;
    }
};

4.运行结果

三、209. 长度最小的子数组

1.题目简介

209. 长度最小的子数组给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

2.解题思路

3.代码

//左闭右开，滑动窗口
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int ret = INT_MAX, left = 0, right = 0, sum = 0;//left左边界，right右边界
        while(right <= nums.size())
        {
            //如果元素和小鱼tar就加上right的元素，同时将right++；
            //如果right是数组最后一个位置的下一个位置(右开)，那么就不存在符合条件的子数组。
            if(sum < target)
            {
                if(right == nums.size()) break;
                sum += nums[right];
                right++;
            }
            else
            {
                if(ret > (right - left))
                {
                    ret = right - left;
                }
                sum -= nums[left];
                left++;
            }
        }
        if(ret == INT_MAX) return 0;
        return ret;
    }
};