15. 3Sum，16. 3Sum Closest，18. 4Sum（最後一個方法重要）重要

第一題、15. 3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:

[

[-1, 0, 1],

[-1, -1, 2]

]

二分查找的思想

vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int> > ret;
        int size = num.size();
        sort(num.begin(), num.end());
        for(int i = ; i < size; i ++)
        {
            //skip same i
            while(i >  && i < size && num[i] == num[i-])
                i ++;
            int j = i + ;
            int k = size - ;
            while(j < k)
            {
                int sum = num[i] + num[j] + num[k];
                if(sum == )
                {
                    vector<int> cur();
                    cur[] = num[i];
                    cur[] = num[j];
                    cur[] = num[k];
                    ret.push_back(cur);
                    j ++;
                    k --;
                    //skip same j
                    while(j < k && num[j] == num[j-])
                        j ++;
                    //skip same k
                    while(k > j && num[k] == num[k+])
                        k --;
                }
                else if(sum < )
                {
                    j ++;

                }
                else
                {
                    k --;

                }
            }
        }
        return ret;
    }
           

第二題：16. 3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

int threeSumClosest(vector<int>& nums, int target) {
        vector<vector<int> > ret;
        int size = nums.size();
        sort(nums.begin(), nums.end());
        int sum = nums[]+nums[]+nums[size-];
        int minDis = sum - target;
        for(int i = ; i < size; i++)
        {
            int j = i + ;
            int k = size -;
            while(j<k)
            {
                sum = nums[i]+nums[j]+nums[k];
                if(abs(sum - target) < abs(minDis))
                {
                    minDis = sum - target;
                }

                //minDis = sum - target;
                if(sum == target)//增加這部分處理，是對于{1,2,3,4,5,6,7} target=10,這種一旦找到1,2,7三個數，則不用繼續周遊，繼續
                {
                    return target;
                }
                else if(sum > target)
                {
                    k--;
                }
                else
                {
                    j++;
                }
            }
        }

        return minDis + target;
    }
           

第三題、18. 4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:

[

[-1, 0, 0, 1],

[-2, -1, 1, 2],

[-2, 0, 0, 2]

]

/*
    對數組排序
    确定四元數中的前兩個（a，b）
    周遊剩餘數組确定兩外兩個（c，d），确定cd時思路跟3Sum确定後兩個資料一樣，二分查找左右逼近。
    在去重時采用set集合
    */
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        set<vector<int>> setRes;
        int len = nums.size();
        sort(nums.begin(),nums.end());
        if(len < )
        {
            return (vector<vector<int>> ());
        }

        /*
        for(int i = 0; i < len; i++)
        {
            for(int j = i + 1; j < len; j++)
        */
        for(int i = ; i < len - ; i++)
        {
            for(int j = i + ; j < len - ; j++)
            {
                //二分查找
                int begin = j + ;
                int end = len -;
                while(begin < end)
                {

                    int sum = nums[i] + nums[j] + nums[begin] + nums[end];
                    if(sum == target)
                    {
                        vector<int> temp;
                        temp.push_back(nums[i]);
                        temp.push_back(nums[j]);
                        temp.push_back(nums[begin]);
                        temp.push_back(nums[end]);
                        setRes.insert(temp);
                        begin++;
                        end--;
                    }
                    else if(sum > target)
                    {
                        end--;
                    }
                    else
                    {
                        begin++;
                    }
                }
            }
        }

        set<vector<int>>::iterator iter;
        for(iter = setRes.begin(); iter!=setRes.end(); iter++)
        {
            result.push_back(*iter);
        }

        return result;

    }
           

時間複雜度更低的代碼：

vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> total;
        int n = nums.size();
        if(n<)  return total;
        sort(nums.begin(),nums.end());
        for(int i=;i<n-;i++)
        {
            if(i>&&nums[i]==nums[i-]) continue;
            if(nums[i]+nums[i+]+nums[i+]+nums[i+]>target) break;
            if(nums[i]+nums[n-]+nums[n-]+nums[n-]<target) continue;
            for(int j=i+;j<n-;j++)
            {
                if(j>i+&&nums[j]==nums[j-]) continue;
                if(nums[i]+nums[j]+nums[j+]+nums[j+]>target) break;
                if(nums[i]+nums[j]+nums[n-]+nums[n-]<target) continue;
                int left=j+,right=n-;
                while(left<right){
                    int sum=nums[left]+nums[right]+nums[i]+nums[j];
                    if(sum<target) left++;
                    else if(sum>target) right--;
                    else{
                        total.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]});
                        do{left++;}while(nums[left]==nums[left-]&&left<right);
                        do{right--;}while(nums[right]==nums[right+]&&left<right);
                    }
                }
            }
        }
        return total;
    }