[LeetCode]15. 3Sum(Medium)


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

Notice that the solution set must not contain duplicate triplets.

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Time complexity O(N³),O(N*N-1*N-2)

Time complexity O(N²),Two pointer method. After we sort the nums List, nums would be like [-4, -1, -1 , 0, 1, 2]. In the beginning, nums[index] = -4, nums[secondIndex] = -1, and nums[thirdIndex] = 2. We would need complement 4(a+b+c = 0), but the sum of this pair is 3. Since the largest value we can use is 2, so we would let secondIndex plus 1. In orger to generate larger pair sum and vice versa.
How do we avoid the duplicate answer? By skipping nums[index] == nums[index-1]. And when the pair value equals the complement, we would adjust both the secondIndex and thirdIndex, until they both get different value than the pair we get. Hence, we can get the next pair whose pair value equals the complement.




Be Effective and Optimize for Learning

Love podcasts or audiobooks? Learn on the go with our new app.

Native Apps, Hybrid Apps, and Web Apps — A Comparison

Get started with WTForms

Limbo: Scaling Software Collaboration

How we build a successful virtualization stack in 2022

MicroStream + Helidon =  Brave Performance Combination

Meet Alberta: From Learning HTML on NeoPets to Interning at Twitter

Mastering Master Data. How?

HBase Incremental Table Backup and Disaster Recovery Using AWS S3 Storage

fig1. Data backup (https://www.i-evolve.com/our-story/blog/tips-and-considerations-data-backup)

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Sherlock Chiou

Sherlock Chiou

Be Effective and Optimize for Learning

More from Medium

Meme NFT Marketplace In Crypto Space and Role Of MOM

How to use the parameter loop using Zeus network?(A record of the latest progress)

Pinyottas Season One Closeout Raffle

Meta Will Launch An Nft Marketplace — Legacy Research Group