lintcode-57-三数之和

57-三数之和

给出一个有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)

标签

数组排序两根指针脸书

思路

参考资料

首先升序排序数组

然后定义下标变量 k , i , j 。如果简单的遍历，那么跟是否有序没有关系，其时间复杂度将达到O(n^3)。

但是，如果当前选择了a、b、c三个数，如果其和小于目标target，那么需要将其中一个数用更大的数替换；反之亦然。但究竟替换三个数中的哪个数？可以先固定一个数（k），当前值小于target时，可以让 i 增加；否则，j 减小。

code

class Solution {

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> &nums) {

        // write your code here

        int size = nums.size(), target = 0;

        if(size < 3) {

            return vector<vector<int> >();

        }

        vector<vector<int> > result;

        int i = 0, j = 0, k = 0;

        sort(nums.begin(), nums.end());

        for(k=0; k<size; k++) {

            if(k>0 && nums[k]==nums[k-1]) {

                continue;

            }

             for(i=k+1, j=size-1; i<j;) {

                if(i>k+1 && nums[i]==nums[i-1]) {

                    i++;

                    continue;

                }

                if(j<size-1 && nums[j]==nums[j+1]) {

                    j--;

                    continue;

                }

                int sum = nums[i] + nums[j] + nums[k];

                if(target == sum) {

                    vector<int> temp;

                    temp.push_back(nums[k]);

                    temp.push_back(nums[i]);

                    temp.push_back(nums[j]);

                    result.push_back(temp);

                    i++;

                    j--;

                }

                else if(target < sum) {

                    j--;

                }

                else {

                    i++;

                }

            }

        }

        return result;

    }

};

巴特西

lintcode-57-三数之和

57-三数之和

注意事项

样例

标签

思路

code

最新文章

热门文章