N-sum趣题

发表于 | 分类于 | 评论数：

N-sum Problem

源代码push到了github上,戳这里

N-sum 专题

1 sum

题目描述:在给定序列里寻找一个数,使之等于target,返回该数.
解法:将数组排序,二分查找, 时间复杂度O(logn)

Binary Search
1
2
3
4
5
6
7
8
9
10
11
12
int binary_search(int a[],int n,int target)
{
	int l = 0, r = n - 1, mid;
    while(l <= r)
    {
    	mid = (l + r) >> 1;
        if(a[mid] == target) return a[mid];
        else if(a[mid] > target) r = mid - 1;
        else l = mid + 1;
    }
    return -1;
}

解法二: 当然,如果找到一个比较好的hash函数或者hashtable, O(1)的复杂度就可以找到.
下述所有的涉及二分查找的方法都可以用hash法代替,故不讨论.

2 sum

题目描述: 在给定序列中寻找所有满足且不重复的元组(x,y),x <= y,使得 x + y == target
解法一: 参照 1 sum 的思路,先排序,固定住a,此时只要在数组中二分寻找存不存在数(target - x)即可

解法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<vector<int> > two_sum_one(int a[],int n,int target)
{
	vector<vector<int> > ans;
	//fix x
    for(int i = 0; i < n; i++)
    {
    	int tmp = binary_search(a,n,target - a[i]);
        if(tmp == -1 || tmp == i)continue;
        else
        {
        	//find a solution
            vector<int> tmpans;
            tmpans.push_back(x);
            tmpans.push_back(y);
            ans.push_back(tmpans);
        }
    }
    //remove the duplicate answer in vector ans
    //we can sort vector ans and do the remove action
    return ans;
}

解法二: 对于一个有序数组 a <= b <= c <= d, 我们可以发现以下的不等式成立:

a + d <= b + d  
a + d >= a + c

设想如果有两个指针start,end, start指向a, end指向d,如果此时start + end < target,那么依据上面的不等式,只需要将start指针迁移,后面的和一定比前面的和大.这样在O(n)的时间内就可以搞定. 排序的时间复杂度是O(nlogn),那么总的复杂度还是O(nlogn).这种思想在后面会用到.

解法二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<vector<int> > two_sum_two(int a[],int n,int target)
{
	vector<vector<int> > ans;
    for(int i = 0, k = n - 1; i < k;)
    {
    	//this will remove the duplicate answer, think a bit
    	if(i > 0 && a[i] == a[i-1])continue;
        
    	if(a[i] + a[k] == target)
        {
        	//find a solution
            vector<int> tmpans;
            tmpans.push_back(a[i]);
            tmpans.push_back(a[k]);
            ans.push_back(tmpans);
            i++;
            continue;
        }
        else if(a[i] + a[k] < target) i++;
        else k --;
    }
    return ans;
}

3 sum

题目描述: 在给定序列中寻找所有满足且不重复的元组(x,y,z),x <= y <= z,使得 x + y + z == target
经过上面的推导,显然此题也有两种解法.对于解法一,固定住x,y,二分查找z,时间复杂度是O(n2logn).对于解法二,固定住x,问题就便成了2 sum的问题.时间复杂度为O(n2).

4 sum

对于此问题而言,可以延续上面的解法,但是偶数-sum问题可以做一下化简.将数组两两之和求出来,形成新的数组,在新的数组里面只要找出两个数之和等于target即可.即4 sum问题转化为了 2 sum + 2 sum的问题.上述两种方法随便挑.时间复杂度都是O(n2).

N sum

显然,可以将N sum问题拆分成 N - i sum 和 N sum 两个问题求解,酌情考虑.

Leetcode 18: 3Sum

如上面所讨论的,我的实现是采用了第两个指针的方法.

Leetcode 19: 4Sum

如上面讨论,我的实现是转化成了 3 sum 问题,时间复杂度是O(n3).

Leetcode 20: 3Sum Closest

题目描述: 和3 sum不同的唯一一点就是,他要在数组中找3个数,使得和最接近target.输出这个和.
解法:大体思想不变.我用的是两个指针的方法,那么每次只要取 abs(target - sum)的最小值,并在更新的时候记录这个差是正的还是负的(和比target大还是小).

ThreeSumClosest
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
int threeSumClosest(vector<int> &num, int target) {
    int ans = 1e9 +7,flag = 1;
    sort(num.begin(),num.end());
    int len = num.size();
    for(int i = 0; i < len - 2; i++)
    {
        for(int j = i + 1, k = len - 1; j < k;)
        {
            int tmp = num[j] + num[k] + num[i];
            if(tmp < target)
            {
                if(target - tmp < ans)
                {
                    ans = target - tmp;
                    flag = -1;
                }
                j++;
            }
            else
            {
                if(tmp - target < ans)
                {
                    ans = tmp - target;
                    flag = 1;
                }
                k--;
            }
        }
    }
    return target + flag*ans;
}