天天演算法 | Medium | 5. 3Sum : 找出所有和為零的三元組（不重複）

01-28

每天來一道，面試不卡殼，今天是天天演算法陪你成長的第5天

此題可在 leetcode 上 oj，鏈接：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: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],nnA solution set is:n[n [-1, 0, 1],n [-1, -1, 2]n]n

題目翻譯

一個包含n個整數的數組S，判斷S中是否存在元素a + b + c = 0，查找數組中所有和為零的三元組。

注意：解決方案集不能包含重複的三元組。

例如，數組S = [-1,0,1,2,-1,-4]nn答案是：n[n [-1 , 0 , 1],n [-1 , -1 , 2]n]n

解題方案

標籤： Array

思路：

首先對數組進行排序，時間複雜度為O(n*logn)
然後對數組進行兩層的遍歷，先取出當前遍歷的數字為nums[i]，然後從數組兩側取出數字分別為nums[begin]和nums[end]，然後三個數求和值為sum
sum == 0，將三個數加入結果之中，同時將兩側的下標向中間移動，直到不與之前取出的數字相同，避免出現重複的三元組
sum > 0，因為數組有序，說明右側的數字過大，所以下標左移，故而執行end--
sum < 0，因為數組有序，說明左側的數字過小，所以下標右移，所以執行begin++
因為兩層的遍歷時間複雜度為O(n^2)，O(n*logn) + O(n^2) = O(n^2)，所以總體時間複雜度為O(n^2)

代碼：

//javascriptnvar arrSort = function(arr){n arr.sort(function(a,b){n if(a>b) return 1;n else if(a<b) return -1;n return 0;n })n return arr;n}nfunction threeSum(nums){n var arr2 = arrSort(nums);n // let arr2 = Array.from(new Set(arr1))n var length = arr2.length;n let res = [];n for(let index = 0; index<length; index++){n let sum = 0 - arr2[index];n let element = arr2[index];n let i = index + 1, j = arr2.length - 1;n while(i<j){n if(arr2[i] + arr2[j] == sum){n res.push([element, arr2[i],arr2[j]]);n while( i<j & arr2[i] == arr2[i+1]) i++;n while( i<j & arr2[j] == arr2[j+1]) j--;n i++;n j--;n }n while(arr2[i] + arr2[j] < sum) i++;n while(arr2[i] + arr2[j] > sum) j--;n }n while(index<length & arr2[index]==arr2[index+1]) index++;n }n return res;n}n

//javanpublic class Solution { n public List<List<Integer>> threeSum(int[] nums) { n List<List<Integer>> res = new ArrayList<List<Integer>>(); n int len=nums.length; n if(len<3)return res; n Arrays.sort(nums); n for(int i=0;i<len;i++){ n if(nums[i]>0)break; n if(i>0 && nums[i]==nums[i-1])continue; n int begin=i+1,end=len-1; n while(begin<end){ n int sum=nums[i]+nums[begin]+nums[end]; n if(sum==0){ n List<Integer> list = new ArrayList<Integer>(); n list.add(nums[i]);list.add(nums[begin]);list.add(nums[end]); n res.add(list); n begin++;end--; n while(begin<end && nums[begin]==nums[begin-1])begin++; n while(begin<end && nums[end]==nums[end+1])end--; n }else if(sum>0)end--; n else begin++; n } n } n return res; n } n}n

歡迎加入碼蜂社演算法交流群：天天一道演算法題

掃描下方二維碼或搜索「碼蜂社」公眾號，不怕錯過好文章：

如果你支持天天演算法，那就點個贊吧~