betway必威-betway必威官方网站
做最好的网站

最接近的3个数的和,3个数的和

LeetCode 15 3Sum(3个数的和)

翻译

给定一个有n个整数的数组S,是否存在三个元素a,b,c使得a b c=0?
找出该数组中所有不重复的3个数,它们的和为0。

备注:
这三个元素必须是从小到大进行排序。
结果中不能有重复的3个数。

例如,给定数组S={-1 0 1 2 -1 4},一个结果集为:
(-1, 0, 1)
(-1, -1, 2)

原文

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

Note:
Elements in a triplet (a,b,c) must be in non-descending order. 
(ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.

For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:

(-1, 0, 1)
(-1, -1, 2)

经典方法,可惜我并没有想到这样写……

class Solution {
public:
    vector> threeSum(vector& nums) {
        sort(nums.begin(), nums.end());
        vector> result;

        int len = nums.size();      
        for (int current = 0; current < len - 2&&nums[current]<=0;current  )
        {
            int front = current   1, back = len - 1;
            while (front < back)
            {
                if (nums[current]   nums[front]   nums[back] < 0)
                    front  ;
                else if (nums[current]   nums[front]   nums[back] > 0)
                    back--;
                else
                {
                    vector v(3);
                        v.push_back(nums[current]);
                        v.push_back(nums[front]);
                        v.push_back(nums[back]);
                        result.push_back(v);
                        v.clear();
                    do {
                        front  ;
                    } while (front < back&&nums[front - 1] == nums[front]);
                    do {
                        back--;
                    } while (front < back&&nums[back   1] == nums[back]);
                }
            }                    
            while (current < len - 2 && nums[current   1] == nums[current])
                current  ;
        }                                  
        return result;
    }
};

继续努力……

和本道题关联密切的题目推荐:

传送门:LeetCode 16 3Sum Closest(最接近的3个数的和)
传送门:LeetCode 18 4Sum(4个数的和)

 

15 3Sum(3个数的和) 翻译 给定一个有n个整数的数组S,是否存在三个元素a,b,c使得a b c=0?找出该数组中所有不重复的3个数,它们的和...

LeetCode 18 4Sum(4个数的和)

LeetCode 16 3Sum Closest(最接近的3个数的和)

翻译

给定一个有n个数字的数组S,在S中是否存在元素a,b,c和d的和恰好满足a   b   c   d = target。

找出数组中所有的不想等的这四个元素,其和等于target。

备注:

在(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)

翻译

给定一个有n个整数的数组S,找出S中3个数,使其和等于一个给定的数,target。

返回这3个数的和,你可以假定每个输入都有且只有一个结果。

例如,给定S = {-1 2 1 -4},和target = 1。

那么最接近target的和是2。(-1   2   1 = 2)。

本文由betway必威发布于编程开发,转载请注明出处:最接近的3个数的和,3个数的和

TAG标签: betway必威
Ctrl+D 将本页面保存为书签,全面了解最新资讯,方便快捷。