leetcode三数の和と類似問題型(c++)

目次

三数の和

構想

コード

最も近い3数の和

構想

コード

四数の和

構想

コード

三数の和
n個の整数を含む配列numsを与え,numsにa,b,cの3つの要素が存在するか否かを判断し,a+b+c=0とする.条件を満たし、繰り返さないすべての三元グループを見つけます.注意:答えに重複する三元グループは含まれてはいけません.例えば、所与の配列nums=[−1,0,1,2,−1,−4]であり、要求を満たす三元群の集合は、[[−1,0,1],[−1,−1,2]]である.
構想
配列問題の多くは二本指針法で解決され,この問題も例外ではない.このタイプの問題はすべて順番に並べてからやりやすいです.次に点を固定し,二重ポインタで配列を挟んで結果を導く.重複する問題をフィルタリングすることに注意すればよい.すなわち、次が前と等しいときにスキップする.
コード#コード#

class Solution {
public:
    vector> threeSum(vector& nums) 
    {
        vector> ans;//    
        int len=nums.size();//    
        if(len<3)//  3     
            return ans; 
        sort(nums.begin(),nums.end());//  
        for(int i=0;i{nums[i],nums[l],nums[r]});//           
                    while(l+1l&&nums[r]==nums[r-1])//r          
                        --r;
                    ++l;//   ，l r       
                    --r;
                }
                else if(sum<0)//         ，sum<0,  l，sum  
                {
                    ++l;
                }
                else//   0  
                    --r;
            }
            while(i+1

最も近い三数の和
n個の整数を含む配列numsとターゲット値targetが与えられる.numsの3つの整数を見つけて、それらの和がtargetに最も近いようにします.この3つの数の和を返します.各入力セットに一意の答えしか存在しないと仮定します.例えば、所与の配列nums=[-1,2,1,-4]、およびtarget=1.targetに最も近い3つの数の和は2である.(-1 + 2 + 1 = 2).
構想
前の問題と差が少ないタイプは、最も近い数に変えたにすぎず、全体的な考え方は一致しており、知識は現在最も近い値を格納するために変数を多く使っている.
コード#コード#

class Solution {
public:
    int threeSumClosest(vector& nums, int target) 
    {
        int len=nums.size();//      
        if(len<3)//    3，       
            return INT_MIN;
        
        sort(nums.begin(),nums.end());//  
        int sum=nums[0]+nums[1]+nums[2];//      ，             ，              
        if(sum==target)//            ，  
            return target;
        for(int i=0;itarget)//  target，    r，temp  
                    --r;
            }
        }
        return sum;
    }
};

四数の和
n個の整数を含む配列numsとターゲット値targetを与え、numsにa+b+c+dの値がtargetと等しいように4つの要素a,b,c,dが存在するかどうかを判断する.条件を満たし、繰り返さないすべての四元グループを見つけます.注意:答えに重複する四元グループは含まれてはいけません.例:所与の配列nums=[1,0,−1,0,−2,2],target=0.要求を満たす四元群の集合は,[[−1,0,0,1],[−2,−1,1,2],[−2,0,0,2]]である.
構想
同じ問題でもあるが、三数の和は一つの定点計算であり、四数の和は二つの定点計算であるため、一つのサイクルで反復する必要があるほか、他の操作も三数の和と大きく異なる.
コード#コード#

class Solution {
public:
    vector> fourSum(vector& nums, int target) 
    {
        int len=nums.size();//      
        vector> ans;//    
        if(len<4)//  4 ，   
            return ans;
        
        sort(nums.begin(),nums.end());//  
        
        for(int i=0;i{nums[i],nums[j],nums[l],nums[r]});
                        while(l+1l&&nums[r-1]==nums[r])
                            --r;
                        ++l;
                        --r;
                    }
                    else if(sum