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

LeetCode --- 15. 3Sum

編輯:C++入門知識

LeetCode --- 15. 3Sum


題目鏈接:3Sum

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)

這道題的要求是在給定的正整數數組中,找到三個數,使其之和等於0。要求三個數字按照非遞減排列,而且不包含重復的。

這道題的思路和之前的Two Sum差不多,簡單方式是暴力查找,先排序,然後3層循環遍歷數組,時間復雜度O(n3)。優化時,可以先固定一個數,再用兩個指針l和r從這個數後面的兩邊往中間查找,當這三個數之和等於0的時候,記錄一下,當之和大於0的時候,r左移,而當之和小於0的時候,l右移,直到l和r相遇。這個其實就是在Two Sum外層加1層循環,因此時間復雜度是排序的O(nlogn)加O(n2),即O(n2)。

由於三個數字需要按照非遞減序列排放,因此先排序可以滿足此要求。又要求不包含重復元素,因此在選擇第一個數字的時候以及後面兩個指針查找時,需要跳過重復元素。

時間復雜度:O(n2)

空間復雜度:O(1)

 1 class Solution
 2 {
 3 public:
 4     vector > threeSum(vector &num)
 5     {
 6         vector > v;
 7         
 8         if(num.size() == 0)
 9             return v;
10         
11         sort(num.begin(), num.end());
12         
13         for(int i = 0; i < num.size() - 2 && num[i] <= 0; ++ i)
14         {
15             if(i > 0 && num[i] == num[i - 1]) // 跳過重復元素
16                 continue;
17             
18             int l = i + 1, r = num.size() - 1;
19             while(l < r)
20             {
21                 if(num[l] + num[r] == 0 - num[i])
22                 {
23                     v.push_back({num[i], num[l], num[r]});
24                     
25                     ++ l, -- r;
26                     while(l < r && num[l] == num[l - 1]) // 跳過重復元素
27                         ++ l;
28                     while(l < r && num[r] == num[r + 1]) // 跳過重復元素
29                         -- r;
30                 }
31                 else if(num[l] + num[r] > 0 - num[i])
32                     -- r;
33                 else
34                     ++ l;
35             }
36         }
37         
38         return v;
39     }
40 };

 

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