程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode 15 3Sum(3個數的和)

LeetCode 15 3Sum(3個數的和)

編輯:關於C++

翻譯

給定一個有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個數的和)

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved