题目

18. 四数之和 - 力扣（LeetCode）

题解

和三数之和整体思路一样，再加一个for循环，从数组末端开始遍历，需要注意sum用long long定义，因为有一个测试用例卡这个。

输入[1000000000,1000000000,1000000000,1000000000] 

    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
//        for(int num:nums)
//            cout<<num;
        vector<vector<int>>result;
        for(int j=nums.size()-1;j>=0;j--) {
            long long temp=(long long)nums[j]*4;
            if(temp<target)
                break;
            if(j<nums.size()-1&&nums[j]==nums[j+1])
                continue;
            for (int i = 0; i < j-2; i++) {
//                if (nums[i] > target)
//                    break;
                if (i > 0 && nums[i] == nums[i - 1])
                    continue;
                int left = i + 1;
                int right = j - 1;
                while (left < right) {
                    long long sum = (long long )nums[i] + nums[left] + nums[right]+nums[j];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        result.push_back(vector<int>{nums[i], nums[left], nums[right],nums[j]});
                        while (left < right && nums[left] == nums[left + 1])left++;
                        while (left < right && nums[right] == nums[right - 1])right--;
                        right--;
                        left++;
                    }
                }
            }
        }
        return  result;
    }