LeetCodeスナップ:15.3 Sum+16.3 Sum Closest+18.4 Sumソート+ダブルポインタ遍歴問題+アルゴリズム解析+Cpp解答

GitHubリンク:https://github.com/WilliamWuLH/LeetCode
いいと思うなら⭐StarとFork❤
15.3Sum
並べ替え+ダブルポインタ遍歴:
まず、与えられた配列をソートします(小さい順から大きい順).
ソートされた配列の各数を巡回し、この数が前に議論されている場合はスキップできます.
取り出した数を[ターゲット](Target)として、2つのポインタを使用してソートされた配列の他の2つの数を探します.
1つの左ポインタは、その取り出した数の後の数、すなわちこのときの最低位を指す.
もう1つの右ポインタは、配列の最後の数、すなわち、このときの最上位を指します.
配列はすでに小さいから大きいまで並べ替えられているため、このときの3つの数の和はsumになります.

sum>0の場合、右ポインタが指す数が大きすぎて、左に移動するには、指す数が小さくなっても(左に移動した数が前と同じであれば、左に移動し続ける必要があります).

sum<0の場合、左ポインタが指す数が小さすぎることを示し、右に移動するには、指す数が大きくなっても(右に移動した数が以前と同じであれば右に移動し続ける必要がある).

sum=0の場合、答えを見つけ、左ポインタと右ポインタを真ん中に寄せて、新しい答えがあるかどうかを確認します.

class Solution {
public:
    vector> threeSum(vector& nums) {
        int len = nums.size();
        vector> ans;
        sort(nums.begin(),nums.end());
        for(int i=0;i 0 && nums[i-1] == nums[i])
                continue;
            int left = i+1,right = len-1;
            while(left < right){
                int sum = nums[i] + nums[left] + nums[right];
                if(sum > 0)
                    while(left < --right && nums[right] == nums[right+1]);
                else if(sum < 0)
                    while(++left < right && nums[left-1] == nums[left]);
                else{
                    vector temp = {nums[i],nums[left],nums[right]};
                    ans.push_back(temp);
                    while(++left < right && nums[left] == nums[left-1]);
                    while(left < --right && nums[right] == nums[right+1]);
                }
            }
        }
        return ans;
    }
};

16.3Sum Closest
並べ替え+ダブルポインタ遍歴:

class Solution {
public:
    int threeSumClosest(vector& nums, int target) {
        int len = nums.size();
        int ans = nums[0] + nums[1] + nums[2];
        sort(nums.begin(),nums.end());
        for(int i = 0; i < len-2; i++ ){
            if( i > 0 && nums[i] == nums[i-1])
                continue;
            int left = i+1,right = len-1;
            while(left < right){
                int sum = nums[i] + nums[left] + nums[right];
                if(abs(ans - target) > abs(sum - target))
                    ans = sum;
                if(sum > target)
                    while(left < --right && nums[right] == nums[right+1]);
                else if(sum < target)
                    while(++left < right && nums[left] == nums[left-1]);
                else
                    return sum;
            }
        }
        return ans;
    }
};

18.4Sum
並べ替え+ダブルポインタ遍歴:
3 Sumのような問題は、すべて1つの方法で、ただ1つの循環が増えただけです.
いくつかの判断を追加することで、プログラムのパフォーマンスを向上させることができます.

このとき最小の4つの数の加算が目標値よりも大きい場合、ループから直接飛び出すことができる.

この時点で巡回するi番目の数と最大の3番目の数の加算が目標値よりも小さい場合、次のループに直接進むことができる(i番目の数が大きくなる).

class Solution {
public:
    vector> fourSum(vector& nums, int target) {
        vector> ans;
        int len = nums.size();
        sort(nums.begin(),nums.end());
        for(int i=0;i 0 && nums[i] == nums[i-1])
                continue;
            if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target)
                break;
            if(nums[i]+nums[len-1]+nums[len-2]+nums[len-3] < target)
                continue;
            for(int j=i+1;j i+1 && nums[j] == nums[j-1])
                    continue;
                int left = j+1,right = len-1;
                while(left < right){
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if(sum > target)
                        while(left < --right && nums[right] == nums[right+1]);
                    else if(sum < target)
                        while(++left < right && nums[left] == nums[left-1]);
                    else{
                        ans.push_back(vector{nums[i],nums[j],nums[left],nums[right]});
                        while(left < --right && nums[right] == nums[right+1]);
                        while(++left < right && nums[left] == nums[left-1]);
                    }
                }
            }
        }
        return ans;
    }
};