leetcode-18 4sum

題意: 給定數列,求出其中所有四數和為特定值的數組,輸出不可重複

解題思路:其實可以把之前的題目拿來比對一下

之前我們有解過
2 sum, 利用map
3 sum, 轉為 2 sum, 利用map

同理,我們也能把這個題目先轉為3 sum,而後轉2 sum處理, 只是之前解3 sum時, 發現vector 用map實在太慢, 因此這次利用迴圈判定, 來解決數組重複為題,其原理如下,若目前判定的數和前一個相同,則可略過,為什麼呢,因為每個位置只能放一個數,若其與之前相同,則表示此種可能已被判定,故一定要跳過,以免重複

程式碼如下:

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