两数之和 ? 三数之和? 四数之和? 统统搞定

发布时间:2024年01月06日

在这里插入图片描述

🎈个人主页:🎈 :???初阶牛???
🐻推荐专栏1: 🍔🍟🌯C语言初阶
🐻推荐专栏2: 🍔🍟🌯C语言进阶
🔑个人信条: 🌵知行合一

前言

声明:题目来源于: 力扣

一、查找总价格为目标值的两个商品

题目链接:传送门

(1) 题目描述

购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况,返回任一结果即可。

示例

示例 1:

输入:price = [3, 9, 12, 15], target = 18
输出:[3,15] 或者 [15,3]

示例 2:

输入:price = [8, 21, 27, 34, 52, 66], target = 61
输出:[27,34] 或者 [34,27]

(2)解题思路

  1. 定义双指针,left指向最开始的元素,right指向最后一个元素。
    在这里插入图片描述

  2. 如果left+right>target
    在这里插入图片描述
    则我们将右指针向前移动,因为数据是有序的,所以移动右指针,left+right减小
    在这里插入图片描述

  3. 如果left+right<target(如上图)
    则我们将左指针向前移动,因为数据是有序的,所以移动左指针,left+right增大

  4. 循环2、3操作,直到找到left+right=target。

  5. 返回leftright

(3)代码展示:

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        int left=0,right=price.size()-1;
        vector<int> v(2);
        while(left<right){
        	//如果left+right>target
            if(price[left]+price[right]>target){
                right--;
            }如果left+right<target
            else if(price[left]+price[right]<target){
                left++;
            }
            else{	//表明//如果left+right=target,可以返回了
                v[0]=price[left];
                v[1]=price[right];
                break;
            }
        }
        return v;
    }
};

二、三数之和

题目链接:传送门

(1) 题目描述

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

示例

示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]

解释:

nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。

示例 2:

输入:nums = [0,1,1]
输出:[]

解释:唯一可能的三元组和不为 0 。

示例 3:

输入:nums = [0,0,0]
输出:[[0,0,0]]

解释:唯一可能的三元组和为 0 。

(2)解题思路

  1. 为了让我们更好的寻找数,排序是有利于提高我们的查找效率的。
  2. 要找到3个数的和为0,我们只需要固定一个数(end),然后找到两个数的和为-end即可。
  3. 初始化end指针,使其指向最后一个元素
    寻找两个数的和为-end
    (1)初始化left使其指向第一个元素。
    (2)初始化right,使其指向end的前一个元素。
    4 .看到这里,应该不难知道,如何寻找寻找两个数的和为-end ,这不就是第一道题的要求吗?
  4. 如果left>right,表明end为前面的所有可能都已经统计过了,end往前移动一步,继续2、3步骤。

注意:
每次移动leftright包括end的时候,由于我们不能出现互不相同的三元组,所以我们需要跳过相同的元素。

(3)代码展示:

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> vv1;
        sort(nums.begin(), nums.end());	//先对数据进行排序
        int end = nums.size() - 1;		//end从最后一个元素开始查起
        while (end >= 2) {
            int right = end - 1;
            int left = 0;
            //找两个数
            while (left < right) {
                if ((nums[left] + nums[right]) == -nums[end]) {//找到以后
                    vector<int> v1 = { nums[left],nums[right],nums[end] };
                    vv1.push_back(v1);
                    left++, right--;
                    //都要跳过重复元素
                    while (left  < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                }
                if ((nums[left] + nums[right]) > -nums[end]) right--;
                else if ((nums[left] + nums[right]) < -nums[end])left++;
            }
            //end也要跳过重复元素
            end--;
            while (end - 1 > 0 && nums[end] == nums[end + 1]) end--;

        }
        return vv1;
    }
};

三、四数之和

题目链接:传送门

(1) 题目描述

给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复):

0 <= a, b, c, d < n
a、b、c 和 d 互不相同 (牛牛提醒一下,这里abcd是下标,而不是数组中的值)
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。

示例:

示例 1:

输入:nums = [1,0,-1,0,-2,2], target = 0
输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2:

输入:nums = [2,2,2,2,2], target = 8
输出:[[2,2,2,2]]

(2)解题思路

牛牛讲不动了,相信大家可以自己写出来的。
在这里插入图片描述

如果直接写第四题,我们可能无法下手,但是有了前两个的铺垫,现在写应该不算太困难了。

秘诀:
四数之和转化为三数之和
三数之和转化为两数之和

(3)代码展示:

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> vv1;
        sort(nums.begin(), nums.end());
        int d = nums.size() - 1;
        while (d >= 3) {
           int c=d-1;
           //找三个数
            while(c>=2){
                int a=0,b=c-1;
                //找两个数
                while (a < b) {
                //找到以后
                if (((long long )nums[a] + nums[b]+nums[c]+nums[d]) == (long long)target) {
                    vector<int> v1 = { nums[a],nums[b],nums[c],nums[d] };
                    vv1.push_back(v1);
                    a++, b--;
                    while (a  < b && nums[a] == nums[a - 1]) a++;
                    while (a < b && nums[b] == nums[b + 1]) b--;
                }
                if ((long long )(nums[a] + nums[b]) > (long long)target-nums[d]-nums[c]) b--;
                else if ((long long )(nums[a] + nums[b]) < (long long )target-nums[d]-nums[c])a++;
                }
            c--;
            while (c  > 0 && nums[c] == nums[c + 1]) c--;
            }
        d--;
         while (d  > 0 && nums[d] == nums[d + 1]) d--;
        }
        return vv1;
    }
};

好了,今天的算法题就到这里了,我们下次见!
在这里插入图片描述

文章来源:https://blog.csdn.net/qq_67276605/article/details/134772380
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。