LeetCode中关于求和的汇总

LeetCode中出现了多个对数据求和的题目，包括Two Sum,Two Sum II, 3Sum,4Sum,4SumII。放在一块统一分析处理。

1. Two Sum

之前的博客分析见这里。

题目描述：

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

解析：显而易见的一种做法是采用两层循环，外出遍历数组中的每个数字i，内层从当前数字往后一直到数组末尾的每个数字j，挨个比对i和j之和是否为target。这样的时间复杂度为\(O(n^{2})\)。然后考虑有没有时间复杂度更低的解法，常用的一种解法是空间换时间。

解法1：

采用Map的形式，key为每个元素，value为每个元素的下标，遍历每个元素i，然后判断target-i是否也在map中，如果在则直接返回。具体代码如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {      
        vector<int> result;
        if(nums.size() <= 1)
            return result;
        unordered_map<int,int> tempMap;//hash_map key元素,value下标
        for(int i = 0; i < nums.size(); ++i)
            tempMap[nums[i]] = i;
        for(int i = 0; i < nums.size(); ++i)
        {
            int another = target - nums[i];
            if(tempMap.find(another)!=tempMap.end())
            {
                int index = tempMap[another];
                if(index == i)//元素不能相同
                    continue;    
                if(index < i)
                {
                    result.push_back(index);  
                    result.push_back(i);
                    return result;
                }
                else
                {
                    result.push_back(i);
                    result.push_back(index);
                    return result;
                }
            }
        }
    }
};

解法2：

思路跟上面的题目一致，只不过代码更简洁，并且也不用提前把所有的元素先插入到map中，在循环数组的时候进行处理，另外还不必判断数组下标的大小，判断当前元素下标i的时候，如果另一个元素在Map中出现，因为下标由小到大的，那下标必然比i小。

代码如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> tools;
        for(int i=0; i < nums.size(); i++)
        {
            int another = target-nums[i];
            if(tools.find(another) != tools.end())
                return {tools[another], i};
            tools[nums[i]] = i;
        }
        return {};
    }
};

两种方法的时间对比如下：

2. Two Sum II – Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

• Your returned answers (both index1 and index2) are not zero-based.
• You may assume that each input would have exactly one solution and you may not use the same element twice.

Example:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

解析：相对于上一个题目，这里输入的数组是已经排好序的，既然数组已经排好序，所以考虑双指针法，定义low和high，查看nums[low]+nums[high]与target之间的关系。代码如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int low = 0, high = numbers.size()-1;
        while(low <= high)
        {
            if(numbers[low] + numbers[high] == target)
                return {low+1, high+1};
            else if(numbers[low] + numbers[high] < target)
                low ++;
            else 
                high --;
        }
        return {};
    }
};

3.3Sum

Given an array nums of n integers, are there elements a, b, c in nums  such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解析：三个数的求和，要求不得有重复结果。转换为Two Sum，对于每一个a，计算b+c=-a，返回的结果是由小到大排序，并且不能有重复元素，所以首先对数组进行排序。具体代码如下：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector< vector<int> > results;
        if(nums.size() < 3)
            return results;
        sort(nums.begin(), nums.end());//数组排序
        for(int index = 0; index < nums.size()-2; index ++)
        {
            if(index >0 && nums[index] == nums[index-1])//过滤掉相同元素
                continue;
            int target = -nums[index];
            vector<vector<int>> item_result = twoSum(nums, index, target);
            if(item_result.size() > 0)
                results.insert(results.end(), item_result.begin(), item_result.end());
        }
        return results;
    }
    vector< vector<int> > twoSum(vector<int>& nums, int begin, int target) {//二分查找法
        vector< vector<int> > results;
        int low = begin + 1;
        int high = nums.size()-1;
        while(low < high)
        {
            int sum = nums[low] + nums[high];
            if(sum == target)
            {
                vector<int> item_result;
                item_result.push_back(nums[begin]);
                item_result.push_back(nums[low]);
                item_result.push_back(nums[high]);
                results.push_back(item_result);
                do{//重复元素跳过
                    low ++;
                }while(low < high && nums[low] == nums[low-1]);
                do{
                    high --;
                }while(low < high && nums[high] == nums[high+1]);
            }else if(sum < target)
                low ++;
            else
                high --;
        }        
        return results;
    }
};

4.3Sum Closest

Given an array nums of n integers and an integer target, find three integers in nums  such that the sum is closest to target . Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

解析：

这个题目是要求最接近target的结果。这里也是采用的指针法，外层遍历每一个元素，然后采用双指针计算另外两个元素的和，定义变量gap来表示三个元素和与目标元素的差值。也是首先进行排序，代码如下：

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int size  = nums.size();
        int result = 0;
        int gap =INT_MAX;
        for(int index = 0; index < size-2; index ++)
        {
            int low = index + 1;
            int high = size -1;
            while(low < high)
            {
                int sum = nums[index] + nums[low] + nums[high];
                int min_gap = abs(sum-target);
                if(min_gap < gap)
                {
                    gap = min_gap;
                    result = sum;
                }
                if(sum < target)
                    low ++;
                else{
                    high --;
                }
            }
        }
        return result;
    }
};

5. 4sum

Given an array nums  of n integers and an integer target , are there elements a, b, c, and d in nums  such that a + b + c + d = target ? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

解析：

4个元素求和，如果4层循环，那时间复杂度太高，这里考虑空间换时间，首先对数组排序，然后计算两两元素之和，存放于map中，其中key为sum，value为index数组，然后两两元素挨个计算求和，看target-sum是否在map中。代码如下：

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector< vector<int>> results;
        sort(nums.begin(), nums.end());
        unordered_map<int, vector<pair<int, int>>> two_sum_map;
        for(int i =0; i < nums.size(); i ++)
        {
            for(int j=i+1; j < nums.size(); j++)
            {
                int sum = nums[i] + nums[j];
                two_sum_map[sum].push_back(pair<int, int>(i, j));
            }
        }
        for(int index = 0; index < nums.size(); index ++)
        {
            for(int j=index + 1; j < nums.size(); j++)
            {
                int temp_target = target - nums[index] - nums[j];
                if(two_sum_map.find(temp_target) != two_sum_map.end())
                {                    
                    auto& vec = two_sum_map[temp_target];
                    for(auto& vec_item : vec)
                    {
                        if(j >= vec_item.first) 
                            continue;
                        vector<int> item_result;
                        item_result.push_back(nums[index]);
                        item_result.push_back(nums[j]);
                        item_result.push_back(nums[vec_item.first]);
                        item_result.push_back(nums[vec_item.second]);
                        results.push_back(item_result);
                    }
                }
            }
        }
        sort(results.begin(), results.end());
        results.erase(unique(results.begin(), results.end()),results.end());
        return results;
    }
     
};

6. 4Sum II

Given four lists A, B, C, D of integer values, compute how many tuples (i, j ,k l)  there are such that A[i] + B[j] + C[k] + D[l]  is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -2²⁸ to 2²⁸ – 1 and the result is guaranteed to be at most 2³¹ – 1.

Example:

Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:
2

Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

解析：

这道题目也是4个元素求和等于目标值，只不过是4个元素分别来自不同的数组。同上一个题目也是考虑空间换时间，思路同上，直接看代码吧：

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        int counts = 0;
        unordered_map<int, int> maps;
        for(auto a : A)
        {
            for(auto b : B)
            {
                int sum = a + b;
                maps[sum] ++;
            }
        }
        for(auto c : C)
        {
            for(auto d : D)
            {
                int temp_target = 0 - c - d;
                if(maps.find(temp_target) != maps.end())
                {
                    counts += maps[temp_target];
                }
            }
        }
        return counts;
    }
};