刷题笔记 day6-Toy模板网

这篇具有很好参考价值的文章主要介绍了刷题笔记 day6。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

力扣 57 和为s的两个整数

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int>  v;
        int i =0 , j = nums.size()-1;
        while(i < j)
        {
            if(nums[i]+ nums[j] > target)
            {
                --j;
            }else if(nums[i] + nums[j] < target)
            {
                ++i;
            }else{
                v.push_back(nums[i]);
                v.push_back(nums[j]);
                break;
            }
        }
        return v;
    }
};

对于一个递增排序的数组，我们可以使用双指针；

定义指针 left 指向数组最左端元素，定义指针 right 指向数组最右端元素；

当 nums[left] + nums[right] > target 时，右移指针right;

当 nums[left] + nums[right] < target 时，左移指针left;

当 nums[left] + nums[right] == target 时，输出结果。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int>  v;
        int i =0 , j = nums.size()-1;
        while(i < j)
        {
            if(nums[i]+ nums[j] > target)
            {
                --j;
            }else if(nums[i] + nums[j] < target)
            {
                ++i;
            }else{
                v.push_back(nums[i]);
                v.push_back(nums[j]);
                break;
            }
        }
        return v;
    }
};

力扣 15 三数之和

刷题笔记 day6,数据结构,C++,笔记,leetcode,数据结构

思路：1. 先给数组排序（升序）

2. 固定最右端的数 a；

3. 将数a左边的区间两端定义双指针 left 和 right , 求这三个数（a, nums[left],nums[right）之和是否等于0；大于0 ，右移right ; 小于 0 ，左移 left.

由于输出结果中不能含有重复性元素，所以在算法过程中要去重。

1. 找到一种结果后， left 和 right 要跳过重复元素。

2. 使用完一次双指针后，下一次固定的数不能重复。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        //先排序
        sort(nums.begin(),nums.end());
        vector<vector<int>> v;
        int c = nums.size()-1;
        while( c>=2)
        {
            if(nums[c] < 0) // 如果最大的数小于0，那么将不存在三个数之和为零的情况
            {
                return v;
            }
            int left = 0, right = c-1;
            while(left < right)
            {
                if(nums[left]+nums[right]+nums[c] >0)
                {
                    --right;
                }else if(nums[left]+nums[right]+nums[c] <0){
                    ++left;
                }else{
                    v.push_back({nums[left],nums[right],nums[c]});
                    ++left;
                    while(left < right&& nums[left] == nums[left-1])  //left不能越界
                    {
                        ++left;
                    }
                    --right;
                    while(left < right && nums[right] == nums[right+1])//right不能越界
                    {
                        --right;
                    }
                }
            }
            --c;
            while(c >= 2 && nums[c] == nums[c+1]) //c不能越界
            {
                --c;
            }
        }
        return v;
      }
};

力扣 18 四数之和

刷题笔记 day6,数据结构,C++,笔记,leetcode,数据结构

思路：

这道题的解题方法和上一道题一样。文章来源地址https://www.toymoban.com/news/detail-636496.html

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> v;
        int c = nums.size()-1;
        while(c>=3)
        {
            int  b = c-1;
            while(b>=2)
            {
                int left = 0 , right  = b-1;
                while(left < right)
                {
                    long long sum =(long long) nums[left] + nums[right] + nums[b] + nums[c];
                    if(sum > target)
                    {
                        --right;
                    }else if(sum < target)
                    {
                        ++left;
                    }else{
                        v.push_back({nums[left],nums[right],nums[b],nums[c]});
                        ++left;
                        while(left < right && nums[left] == nums[left-1])
                        {
                            ++left;
                        }
                        --right;
                        while(left < right && nums[right] == nums[right +1])
                        {
                            --right;
                        }
                    }
                }
                --b;
                while(b >=2 && nums[b] == nums[b+1])
                {
                    --b;
                }
            }
            --c;
             while(c >=3 && nums[c] == nums[c+1])
                {
                    --c;
                }
        }
        return v;
    }
};

到了这里，关于刷题笔记 day6的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！