Peiqin Lin's Homepage

KSum 问题系列

2018/10/29 Algorithm

KSum 问题是常见的面试题，包括 2Sum、3Sum 和 4Sum 等。下面我们通过几道 LeetCode 的问题来看一下。

Two Sum

Description

https://leetcode.com/problems/two-sum/

Solution

方法一：对每个元素num[i]，求rest = target - num[i]，然后查找数组中是否存在rest，时间复杂度为O(n^2)。

方法二：利用 hash，可以把查询一个数是否存在的时间复杂度降至O(1)，从而把总时间复杂度降至O(n)。从 C++11 起，STL 提供了基于 hash 表的unordered_map，区别于基于平衡二叉树的map。由于一个数并不能使用两次，所以不能一开始就把数组全都添加到 hash 表中，而应该一边遍历一边加入，每个元素只查找在它之前的元素，因此对于一组数，当遍历到第二个数的时候才能知道结果。

Code
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int>ans;
        unordered_map<int, int>myMap;
        unordered_map<int, int>::iterator it;

        int len = nums.size();
        for(int i = 0; i < len; i ++) {
            it = myMap.find(target - nums[i]);
            if(it != myMap.end()) {
                ans.push_back(it->second);
                ans.push_back(i);
                return ans;
            }
            myMap[nums[i]] = i;
        }
        return ans;
    }
};

int main() {
    Solution *s = new Solution();
    vector<int> nums{1 ,2, 3, 4};
    int target = 7;
    auto ans = s->twoSum(nums, target);
    for(auto a: ans) {
        cout << a << endl;
    }
}

3Sum

Description

https://leetcode.com/problems/3sum/

Solution

由于要求三元组不能重复，所以可以考虑先对数组进行排序，这样子容易发现重复结果，因为当前数与上一个数相同时，我们可以跳过此数的处理。

第一层的遍历表示基准的选择，从而将问题转换为在当前基准后面的数查找所有可能的二元组，使得两个数相加的和等于基准的负数。由于已经进行了排序，所以无需借助 hash 表，就可以以O(n)的时间复杂度实现所有可能二元组的查找。

Code
#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;

class Solution {
public:

    vector<vector<int>> twoSum(vector<int> & nums, int start, int end) {
        vector<vector<int>> ans;
        int sum = 0 - nums[start - 1];

        while(start < end) {
            vector<int>temp;
            temp.push_back(0 - sum);
            if(nums[start] + nums[end] == sum) {
                temp.push_back(nums[start]);
                temp.push_back(nums[end]);
                start ++;
                while(start < end && nums[start] == nums[start - 1]) {
                    start ++;
                }
                end --;
                while(start < end && nums[end] == nums[end + 1]) {
                    end --;
                }
            } else if(nums[start] + nums[end] < sum) {
                start ++;
                while(start < end && nums[start] == nums[start - 1]) {
                    start ++;
                }
            } else if(nums[start] + nums[end] > sum) {
                end --;
                while(start < end && nums[end] == nums[end + 1]) {
                    end --;
                }
            }
            if(temp.size() != 1) {
                ans.push_back(temp);
            }
        }
        return ans;
    }

    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;

        sort(nums.begin(), nums.end());
        int len = nums.size();
        for(int i = 0; i < len - 2; i ++) {
            while(i > 0 && i < len - 2 && nums[i] == nums[i - 1]) {
                i ++;
            }
            vector<vector<int>> temp = twoSum(nums, i + 1, len - 1);
            if(temp.size() != 0) {
                ans.insert(ans.end(), temp.begin(), temp.end());
            }
        }
        return ans;
    }
};

int main() {
    Solution *s = new Solution();
    vector<int> nums{-1, 0, 1, 2, -1, -4};
    auto ans = s->threeSum(nums);
    for(auto vec : ans) {
        for(auto v : vec) {
            cout << v << " ";
        }
        cout << endl;
    }
}

3Sum Closest

Description

https://leetcode.com/problems/3sum-closest/

Solution

这题与 3Sum 十分相似，只要把原先查找确定的值改成每次遍历的时候比较最小距离即可。

Code
#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;

class Solution {
public:

    void twoSum(vector<int> & nums, int start, int end, int target) {

        int sum = target - nums[start - 1];

        while(start < end) {
            if(abs(ans - target) > abs(nums[start] + nums[end] - sum)) {
                ans = nums[start] + nums[end] - sum + target;
            }

            if(nums[start] + nums[end] == sum) {
                ans = target;
                return ;
            } else if(nums[start] + nums[end] < sum) {
                start ++;
                while(start < end && nums[start] == nums[start - 1]) {
                    start ++;
                }
            } else if(nums[start] + nums[end] > sum) {
                end --;
                while(start < end && nums[end] == nums[end + 1]) {
                    end --;
                }
            }
        }
    }

    int threeSumClosest(vector<int>& nums, int target)  {
        ans = nums[0] + nums[1] + nums[2];

        sort(nums.begin(), nums.end());
        int len = nums.size();
        for(int i = 0; i < len - 2; i ++) {
            while(i > 0 && i < len - 2 && nums[i] == nums[i - 1]) {
                i ++;
            }
            twoSum(nums, i + 1, len - 1, target);
        }
        return ans;
    }
private:
    int ans;
};

int main() {
    Solution *s = new Solution();
    vector<int> nums{-1, 2, 1, -4};
    int target = 1;
    auto ans = s->threeSumClosest(nums, target);
    cout << ans << endl;
}

4Sum

Description

https://leetcode.com/problems/4sum/

Solution

这题与 3Sum 十分相似，只要把原先一层的遍历改成两层即可。

Code
#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;

class Solution {
public:

    void twoSum(vector<int> & nums, int start, int end, int target) {

        int sum = target - nums[start - 1];

        while(start < end) {
            if(abs(ans - target) > abs(nums[start] + nums[end] - sum)) {
                ans = nums[start] + nums[end] - sum + target;
            }

            if(nums[start] + nums[end] == sum) {
                ans = target;
                return ;
            } else if(nums[start] + nums[end] < sum) {
                start ++;
                while(start < end && nums[start] == nums[start - 1]) {
                    start ++;
                }
            } else if(nums[start] + nums[end] > sum) {
                end --;
                while(start < end && nums[end] == nums[end + 1]) {
                    end --;
                }
            }
        }
    }

    int threeSumClosest(vector<int>& nums, int target)  {
        ans = nums[0] + nums[1] + nums[2];

        sort(nums.begin(), nums.end());
        int len = nums.size();
        for(int i = 0; i < len - 2; i ++) {
            while(i > 0 && i < len - 2 && nums[i] == nums[i - 1]) {
                i ++;
            }
            twoSum(nums, i + 1, len - 1, target);
        }
        return ans;
    }
private:
    int ans;
};

int main() {
    Solution *s = new Solution();
    vector<int> nums{-1, 2, 1, -4};
    int target = 1;
    auto ans = s->threeSumClosest(nums, target);
    cout << ans << endl;
}

Search

    Table of Contents