4 Sum

Description

Example

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

class Solution {
public:
    /**
     * @param numbers: Give an array numbersbers of n integer
     * @param target: you need to find four elements that's sum of target
     * @return: Find all unique quadruplets in the array which gives the sum of 
     *          zero.
     */
    vector<vector<int> > fourSum(vector<int> nums, int target) {
        // write your code here
        vector<vector<int>> result;
        if (nums.size() < 4) {
            return result;
        }
        int len = nums.size();
        sort(nums.begin(), nums.end());
        vector<int> row;
        int rest = 0;
        int start = 0;
        int end = 0;
        for (int i = 0; i < len - 3; ++i) {
            // de-dup
            if (i > 0 && nums[i-1] == nums[i]) {
                continue;
            }
            // pruning 
            if (nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target) {
                break;
            }
            if (nums[i] + nums[len-3] + nums[len-2] + nums[len-1] < target) {
                continue;
            }
            for (int j = i + 1; j < len - 2; ++j) {
                // de-dup
                if (j > i + 1 && nums[j-1] == nums[j]) {
                    continue;
                }
                // pruning
                if (nums[i] + nums[j] + nums[j+1] + nums[j+2] > target) {
                    break;
                }
                if (nums[i] + nums[j] + nums[len-2] + nums[len-1] < target) {
                    continue;
                }
                rest = target - nums[i] - nums[j];
                start = j + 1;
                end = len - 1;
                while (start < end) {
                    // de-dup
                    if (start > j + 1 && nums[start-1] == nums[start]) {
                        start++;
                        continue;
                    }
                    if (nums[start] + nums[end] > rest) {
                        end--;
                    } else if (nums[start] + nums[end] < rest) {
                        start++;
                    } else {
                        row.clear();
                        row.push_back(nums[i]);
                        row.push_back(nums[j]);
                        row.push_back(nums[start]);
                        row.push_back(nums[end]);
                        result.push_back(row);
                        start++;
                        end--;
                    }
                } // 2sum
            } // 3sum
        } // 4sum
        return result;
    }
};

Similar problems

x

Tags

x