3 Sum

Description

Example

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

class Solution {
public:    
    /**
     * @param numbers : Give an array numbers of n integer
     * @return : Find all unique triplets in the array which gives the sum of zero.
     */
    vector<vector<int> > threeSum(vector<int> &nums) {
        // write your code here
        vector<vector<int>> result;
        if (nums.size() < 3) {
            return result;
        }
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; ++i) {
            if (i > 0 && nums[i-1] == nums[i]) {
                continue;
            }
            int target = 0 - nums[i];
            int start = i+1;
            int end = n-1;
            while (start < end) {
                if (start > i+1 && nums[start-1] == nums[start]) {
                    ++start;
                    continue;
                }
                if (nums[start] + nums[end] > target) {
                    --end;
                } else if (nums[start] + nums[end] < target) {
                    ++start;
                } else {
                    vector<int> row(3);
                    row[0] = nums[i];
                    row[1] = nums[start];
                    row[2] = nums[end];
                    result.push_back(row);
                    ++start;
                    --end;
                }
            } // 2sum
        } // 3sum
        return result;
    }
};

Similar problems

x

Tags

x