【lintcode】两数之和、三数之和、最接近的三数之和、四数之和小结

不念不忘少年蓝@ 2022-06-05 06:53 209阅读 0赞

## 两数之和 ##

给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。
    你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。
    注意这里下标的范围是 1 到 n，不是以 0 开头。
    你可以假设只有一组答案。
    
    样例
    给出 numbers = [2, 7, 11, 15], target = 9, 返回 [1, 2].

思路：  
我们想到的最简单的方法是使用两个for循环，对于每个元素逐个遍历它后面的元素查找是否有与其相加和为target的元素，显然这样做的时间复杂度为O(n^2)，效率太低。  
这里我们利用哈希表来实现，使用了STL中的容器**unordered\_map**. 这个容器可以用哈希表的形式存储一个< key,value >对，key值被存放在哈希表中，有一个value值与之相对。可以用**map\[key\]**这样的形式访问和存储value.  
所以我们可以将给定数组中的元素及其下标以key和value的形式存入哈希表中。对于一个值key我们只需查找(target-key)是否在哈希表中即可。遍历数组建立哈希表的复杂度为O(n),对哈希表的查找复杂度为O(1)，最后总的时间复杂度即为O(n).  
这里要注意的一点是由于哈希表的特点，相同的key值在哈希表中不能重复存放，如果先建立哈希表再查找的话，对于 \[3,3,4\] 6 这样有重复元素的输入就无法求出正确结果了。所以我们采用先建立一个空的哈希表，然后遍历数组时一边添加，一边查找这样的方式来解决这个问题。

class Solution {
    public:
        /*
         * @param numbers: An array of Integer
         * @param target: target = numbers[index1] + numbers[index2]
         * @return: [index1 + 1, index2 + 1] (index1 < index2)
         */
        vector<int> twoSum(vector<int> &numbers, int target) {
            // write your code here
            unordered_map<int,int> hash;
            vector<int> result;
            result.resize(2);
            result[0] = 0;
            result[1] = 0;
            hash[numbers[0]] = 0;
            for(int i = 1; i < numbers.size(); i++){
                if(hash.find(target-numbers[i]) != hash.end()){
                    result[0] = 1+hash[target-numbers[i]];
                    result[1] = 1+i;
                    return result;
                }
                hash[numbers[i]] = i;
            }
            return result;
        }
    };

## 三数之和 ##

给出一个有n个整数的数组S，在S中找到三个整数a, b, c，找到所有使得a + b + c = 0的三元组。
    在三元组(a, b, c)，要求a <= b <= c。
    结果不能包含重复的三元组。
    
    样例
    如S = {-1 0 1 2 -1 -4}, 你需要返回的三元组集合的是：
    (-1, 0, 1)
    (-1, -1, 2)

思路：  
首先对数组排序，然后遍历数组，对于遍历到的元素用两个指针指向它后面的部分中最大和最小的两个值，然后利用两个指针向中间逼夹，直到找到三个元素之和等于target.

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> &numbers) {
            // write your code here
            int i, l, r;
            vector<vector<int>> result;
            vector<int> temp;
            sort(numbers.begin(), numbers.end());
            if(numbers[0] > 0)
                return result;
            for(i = 0; i < numbers.size(); i++){
                l = i+1;
                r = numbers.size()-1;
                while(l < r){
                    int sum = numbers[i] + numbers[l] + numbers[r];
                    if(sum < 0)
                        l++;
                    else if(sum > 0)
                        r--;
                    else{
                        temp.clear();
                        temp.push_back(numbers[i]);
                        temp.push_back(numbers[l]);
                        temp.push_back(numbers[r]);
                        int flag = 0;
                        for(int j = 0; j < result.size(); j++)
                            if(result[j] == temp)
                                flag = 1;
                        if(!flag)
                            result.push_back(temp);
                        l++;
                        r--;
                    }
                }
            }
            return result;
        }
    };

## 最接近的三数之和 ##

给一个包含 n 个整数的数组 S, 找到和与给定整数 target 最接近的三元组，返回这三个数的和。
    只需要返回三元组之和，无需返回三元组本身
    
    样例
    例如 S = [-1, 2, 1, -4] and target = 1. 和最接近 1 的三元组是 -1 + 2 + 1 = 2.

思路：  
利用与解决三数之和问题类似的思想，利用两个指针对排序后的数组进行逼夹，直到找到最接近的三数之和。

class Solution {
    public:
        /*
         * @param numbers: Give an array numbers of n integer
         * @param target: An integer
         * @return: return the sum of the three integers, the sum closest target.
         */
        int threeSumClosest(vector<int> &numbers, int target) {
            // write your code here
            int l,r,sum,min;
            sort(numbers.begin(), numbers.end());
            sum = 0;
            for(int i = 0; i < numbers.size(); i++){
                l = i + 1;
                r = numbers.size() - 1;
                while(l < r){
                    sum = numbers[i] + numbers[l] + numbers[r];
                    if(i == 0 && l == 1) min = sum;
                    if(abs(sum-target) < abs(min-target)) min = sum;
                    if(sum < target) l++;
                    else if(sum > target) r--;
                    else return sum;
                }
            }
            return min;
        }
    };

## 四数之和 ##

给一个包含n个数的整数数组S，在S中找到所有使得和为给定整数target的四元组(a, b, c, d)。
    四元组(a, b, c, d)中，需要满足a <= b <= c <= d
    答案中不可以包含重复的四元组。
    样例
    例如，对于给定的整数数组S=[1, 0, -1, 0, -2, 2] 和 target=0. 满足要求的四元组集合为：
    (-1, 0, 0, 1)
    (-2, -1, 1, 2)
    (-2, 0, 0, 2)

思路：与三数之和问题类似，只需在外面多加一层循环即可。

class Solution {
    public:
        /*
         * @param numbers: Give an array
         * @param target: An integer
         * @return: Find all unique quadruplets in the array which gives the sum of zero
         */
        vector<vector<int>> fourSum(vector<int> numbers, int target) {
            // write your code here
            int i, j, l, r, sum;
            vector<int> temp;
            vector<vector<int>> result;
            sort(numbers.begin(), numbers.end());
            for(i = 0; i < numbers.size(); i++)
                for(j = i+1; j < numbers.size(); j++){
                    l = j+1;
                    r = numbers.size()-1;
                    while(l < r){
                        sum = numbers[i] + numbers[j] + numbers[l] + numbers[r];
                        if(sum > target)
                            r--;
                        else if(sum < target)
                            l++;
                        else{
                            temp.clear();
                            temp.push_back(numbers[i]);
                            temp.push_back(numbers[j]);
                            temp.push_back(numbers[l]);
                            temp.push_back(numbers[r]);
                            l++;
                            r--;
                            int flag = 0;
                            for(int k = 0; k < result.size(); k++)
                                if(result[k] == temp)
                                    flag = 1;
                            if(!flag)
                                result.push_back(temp);
                        }
                    }
                }
            return result;
        }
    };