Two Sum 系列, 和为s的两个数字系列(2sum)

发表于 | 分类于 | 浏览 次

和为S两个数字

题目来源：剑指offer
题目链接

题目描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

输出描述:

1
对应每个测试案例，输出两个数，小的先输出。

解法1: 使用set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        set<int> iset;
        vector<int> res(2);
        int mul = INT_MAX;
        for(int i=0;i<array.size();i++){
            if(iset.find(sum - array[i])!=iset.end()){
                int temp = array[i] * (sum - array[i]);
                if(temp < mul){
                    mul = temp;
                    res[0] = sum - array[i];
                    res[1] = array[i];
                }
            }
            iset.insert(array[i]);
        }
        
        // 当找不到两个数的和为sum时，如何处理：返回空数组
        if(mul == INT_MAX){
            return {};
        }
        return res;
    }
};

时间复杂度分析

时间复杂度为O(n)
空间复杂度为O(n)

解法2:双指针

思路：数组是有序的，可以用双指针。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        int i = 0, j = array.size() - 1;
        int lo = -1, hi = array.size();
        int mul = INT_MAX;
        while(i < j){
            int tmp = array[i] + array[j];
            if(tmp == sum){
                if(tmp < mul){
                    mul = tmp;
                    lo = i, hi = j;
                }
                ++i, --j;
            }else if(tmp < sum){
                ++i;
            }else{
                --j;
            }
        }
        if(mul == INT_MAX){
            return {};
        }
        return {array[lo], array[hi]};
    }
};

时间复杂度分析

时间复杂度为O(n)
空间复杂度为O(1)

和为S的连续正数序列

题目链接

题目描述

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

输出描述

1
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

解法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        if(sum == 1){
            return {};
        }
        int thisSum = 0;
        vector<vector<int>> res;
        int n = (sum + 1) / 2;
        vector<int> ans(n+1, 0);
        for(int i=1;i<=n;i++){
            thisSum += i;
            ans[i] = thisSum;
        }
        for(int i=0;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(ans[j] - ans[i] == sum){
                    vector<int> tmp;
                    for(int k=i+1;k<=j;k++){
                        tmp.push_back(k);
                    }
                    res.push_back(tmp);
                }
            }
        }
        return res;
    }
};

使用累计和的概念.
ans[i]统计0-i的和.

解法2

AC代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        int l = 1, r = 2;
        int thisSum = l + r;
        vector<vector<int>> res;
        while(l<= (1+sum)/2){
            if(thisSum == sum){
                vector<int> tmp;
                for(int k=l;k<=r;k++){
                    tmp.push_back(k);
                }
                res.push_back(tmp);
            }
            if(thisSum < sum){
                thisSum += ++r;
            }else{
                thisSum -= l++;
            }
        }
        return res;
    }
};

AC代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        int n = (sum + 1) / 2;
        int i = 1, j = 2;
        int thisSum = 1 + 2;
        vector<vector<int>> res;
        while(j <= n){
            if(sum >= thisSum){
                if(sum == thisSum){
                    vector<int> tmp;
                    for(int k = i;k<=j;++k){
                        tmp.push_back(k);
                    }
                    res.push_back(tmp);
                }
                thisSum += ++j;
            }else{
                thisSum -= i++;
            }
        }
        return res;
    }
};

thisSum表示子数组arr[l,…,r]的累加和. 最初, l=1, r =2, 最小的两个连续正数序列的和为1+2=3.所以,将thisSum初始化为3.
循环结束条件为两个数的和大于等于sum时,因此可知,满足这个条件的最大的子数组为[n, n+1], n = (1+sum)/2.因此,需要循环结束条件为l = (1+sum)/2

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:

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

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

此题和上题的区别有两点：

  1. 返回下标，而不是值
  2. 数组不是有序的

若是返回的是值，可以对数组进行排序然后按双指针解。时间复杂度为O(nlogn)。排序的时间复杂度为O(n)。

解法1：暴力破解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int i = 0, j = nums.size()-1;
        for(int i=0;i<nums.size();i++){
            for(int j=i+1;j<nums.size();j++){
                if(nums[i] + nums[j] == target){
                    return {i, j};
                }
            }
        }
        return {};
    }
};

时间复杂度为O(n2)，空间复杂度为O(1)。

解法2：两趟哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> mp;
        for(int i=0;i<nums.size();i++){
            mp[nums[i]] = i;
        }
        for(int i=0;i<nums.size();i++){
            int complement = target - nums[i];
            if(mp.find(complement)!= mp.end() && mp[complement]!=i){
                return {i, mp[complement]};
            }
        }
        return {};
    }
};

时间复杂度为O(n)，空间复杂度为O(n)。

解法3：一趟哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> mp;
        for(int i=0;i<nums.size();i++){
            int complement = target - nums[i];
            if(mp.find(complement)!=mp.end()){
                return {mp[complement], i};
            }
            mp[nums[i]] = i;
        }
        return {};
    }
};

时间复杂度为O(n)，空间复杂度为O(n)。

3Sum

Medium

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:

1
2
3
4
5
6
7
Given array nums = [-1, 0, 1, 2, -1, -4],

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

思路：首先对数组进行排序。然后锁定第一个数，如第一个数的索引是i，则此后在front-back范围内（front > i）寻找两个数，使他们的和为0 - nums[i]。随着i后移，front和back指定的范围在缩小。因为nums[i]增大，则0 - nums[i]减小。且移动过程中需要去重。

如将上例数据改为：

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

则排序后：

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

过程如下：注意去重

i = 0, front = 1, back = 9, 在front-back中找两个数的和为4
front = 5, back= 9, nums[5]=1, nums[9]=3(front = 6, nums[front]=1，需要去重)
front = 7, back=8, nums[7]=2, nums[8]=2
i = 1, front = 1, back = 9, 在front-back中找两个数的和为1
front = 2, back = 8, nums[2] = -1, nums[8] = 2
front = 3, back = 6, nums[3] = 0, nums[6] = 1(后面back=5, nums[5]=0, 需要去重)
i = 2(nums[2] = -1需要去重)

此题的难点主要在于如何消除重复元素的影响。

有点问题的代码：此代码的问题在于，没有考虑到重复元素的问题。例如

nums = [0,0,0,0]
solution set is [[0,0,0], [0, 0, 0]]
对于考虑到了外重循环遇到重复元素的问题，即对于索引0处的元素和索引1,2,3处的元素都相同，因此，不再统计由索引1,2,3处元素开始的子集合。但是对于内重循环未考虑到当第一个元素确定时，第二个元素和第三个元素重复的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        if(nums.empty()){
            return {};
        }
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        int pre;
        map<int, int> count;
        for(int i=0;i<nums.size();++i){
            if(nums[i] > 0){
                break;
            }
            if(i && nums[i] == pre){
                continue;
            }
            pre = nums[i];
            int complement = 0 - nums[i];
            count.clear();
            for(int j=i+1;j<nums.size();++j){
                int target = complement - nums[j];
                if(count.find(target) !=count.end()){
                    int pos = count[target];
                    res.push_back({nums[i], nums[pos], nums[j]});
                }
                count[nums[j]] = j;
            }
        }
        return res;
    }
};

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        if(nums.empty()){
            return {};
        }
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        int pre;
        map<int, int> count;
        for(int i=0;i<nums.size();++i){
            if(nums[i] > 0){
                break;
            }
            if(i && nums[i] == pre){
                continue;
            }
            pre = nums[i];
            int complement = 0 - nums[i];
            int j = i + 1, k = nums.size() - 1;
            while(j < k){
                if(nums[j] + nums[k] == complement){
                    res.push_back({nums[i], nums[j], nums[k]});
                    while(j < k && nums[j] == nums[j+1]){
                        ++j;
                    }
                    while(j < k && nums[k] == nums[k-1]){
                        --k;
                    }
                    ++j, --k;
                }else if(nums[j] + nums[k] > complement){
                    --k;
                }else{
                    ++j;
                }
            }
        }
        return res;
    }
};

相关题目

在未排序正数数组中累加和为给定值的最长子数组长度